HDU3832 Earth Hour 2011 Multi-University Training Contest 1 - Host by HNU

題目位址：http://acm.hdu.edu.cn/showproblem.php?pid=3832

題意：有n塊區域，求保證前三個區域聯通的情況下最多可以删掉幾個區域；

可以想象最優連通方案不是一條鍊就是一個三叉。因為是無權的，最少點數實際上就是最短路。當分叉點在特定點上的時候，三叉就退化為一條鍊，是以我們隻需要枚舉分叉點即可。

先3次bfs求出各個點到0，1，2三個區域的最短路，然後枚舉點求聯通最小量

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
#define eps 1e-6
#define INF 1000000
struct Point
{
    double x,y,r;
}p[230];
int n,d[3][230],map[230][230];
int vis[230];
double dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init()
{
    scanf("%d",&n);
    memset(map,0,sizeof(map));
    for(int i=0;i<3;i++)
    for(int j=0;j<n;j++)
    d[i][j]=INF;
    d[0][0]=0;
    d[1][1]=0;
    d[2][2]=0;
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);
    }
    for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
    {
        if(dis(p[i],p[j])-p[i].r-p[j].r<=eps)
        {
            map[i][j]=1;
            map[j][i]=1;                                   // 在有公共區域的圓之間建邊
        }
    }

}
void bfs(int k)
{
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(k);
    vis[k]=1;
    d[k][k]=0;
    while(!q.empty())
    {
         int x=q.front();q.pop();

         for(int i=0;i<n;i++)
         if(!vis[i]&&map[x][i])
         {
             vis[i]=1;
             d[k][i]=d[k][x]+1;
             q.push(i);
         }
    }
}

int main()
{
    int Case;
    scanf("%d",&Case);
    while(Case--)
    {
        init();
        int ans=INF;
        bfs(0);
        bfs(1);
        bfs(2);
        for(int i=0;i<n;i++)                           //枚舉分叉點（也包括鍊的情況）
        {
            if(d[1][i]+d[2][i]+d[0][i]+1<ans)
            ans=d[1][i]+d[2][i]+d[0][i]+1;
        }
        if(ans==INF)printf("-1\n");
        else printf("%d\n",n-ans);
    }
return 0;
}