Earth Hour

3
5
1 1 1
1 4 1
4 1 1
2 2 1
3 3 1
7
1 1 1
4 1 1
2 4 1
1 3 1
3 1 1
3 3 1
4 3 1
6
1 1 1
5 1 1
5 5 1
3 1 2
5 3 2
3 3 1

-1
2
1

每个灯看做一个点，能互相照亮的点连边。从0、1、2三个源点求最短路，然后枚举这3个点到每个点的最短距离，得到答案。

#include"stdio.h"
#include"string.h"
#include"queue"
#include"vector"
#include"algorithm"
using namespace std;
#define N 205
const int inf=1000000;
int min(int a,int b)
{
    return a<b?a:b;
}
struct node
{
    int x,y,r;
}p[N];
int g[N][N];
int d[3][N];
int judge(int i,int j)   //判断两个灯是否相交
{
    int x,y,d,r;
    x=p[i].x-p[j].x;
    y=p[i].y-p[j].y;
    d=x*x+y*y;
    r=p[i].r+p[j].r;
    if(r*r>=d)
        return 1;
    return 0;
}
void spfa(int s,int n,int *dis)
{
    int i,mark[N];
    memset(mark,0,sizeof(mark));
    for(i=0;i<n;i++)
        dis[i]=inf;
    dis[s]=0;
    queue<int>q;
    q.push(s);
    mark[s]=1;
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        mark[s]=0;
        for(i=0;i<n;i++)
        {
            if(dis[i]>dis[s]+g[s][i])
            {
                dis[i]=dis[s]+g[s][i];
                if(!mark[i])
                {
                    mark[i]=1;
                    q.push(i);
                }
            }
        }
    }
}
int main()
{
    int T,i,j,x,y,r,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&r);
            p[i].x=x;p[i].y=y;p[i].r=r;
        }
        for(i=0;i<n;i++)
        {
            g[i][i]=0;
            for(j=0;j<i;j++)
            {
                if(judge(i,j))
                    g[i][j]=g[j][i]=1;
                else
                    g[i][j]=g[j][i]=inf;
            }
        }
        spfa(0,n,d[0]);
        spfa(1,n,d[1]);
        spfa(2,n,d[2]);
        int ans=inf;
        for(i=0;i<n;i++)
        {
            ans=min(ans,d[0][i]+d[1][i]+d[2][i]);
        }
        if(ans<inf)
            printf("%d\n",n-ans-1);
        else
            printf("-1\n");
    }
    return 0;
}

hdu 3832 Earth Hour （最短路变形）,布布扣,bubuko.com

hdu 3832 Earth Hour （最短路变形）

原文：http://blog.csdn.net/u011721440/article/details/38490803