Earth Hour(最短路)

　　　　　　　　　　Earth Hour

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 1970 Accepted Submission(s): 781

Problem Description

Earth Hour is an annual international event created by the WWF (World Wide Fund for Nature/World Wildlife Fund), held on the last Saturday of March, that asks households and businesses to turn off their non-essential lights and electrical appliances for one hour to raise awareness towards the need to take action on climate change.
To respond to the event of this year, the manager of Hunan University campus decides to turn off some street lights at night. Each street light can be viewed as a point in a plane, which casts flash in a circular area with certain radius.
What's more, if two illuminated circles share one intersection or a point, they can be regarded as connected.
Now the manager wants to turn off as many lights as possible, guaranteeing that the illuminated area of the library, the study room and the dormitory are still connected(directly or indirectly). So, at least the lights in these three places will not be turned off.

Input

The first line contains a single integer T, which tells you there are T cases followed.
In each case:
The first line is an integer N( 3<=N<=200 ), means there are N street lights at total.
Then there are N lines: each line contain 3 integers, X,Y,R,( 1<=X,Y,R<=1000 ), means the light in position(X,Y) can illuminate a circle area with the radius of R. Note that the 1st of the N lines is corresponding to the library, the 2nd line is corresponding to the study room, and the 3rd line is corresponding to the dorm.

Output

One case per line, output the maximal number of lights that can be turned off.
Note that if none of the lights is turned off and the three places are still not connected. Just output -1.

Sample Input

1 1 1

1 4 1

4 1 1

2 2 1

3 3 1

1 1 1

4 1 1

2 4 1

1 3 1

3 1 1

3 3 1

4 3 1

1 1 1

5 1 1

5 5 1

3 1 2

5 3 2

3 3 1

Sample Output

-1

T 个数据，2D 平面内 n (>=3)个点，再 n 行 x , y , r 表示（x,y）位置的灯照射半径为 r ，要 1 ，2 , 3 点，连通并都照亮，问最多可以关掉几盏灯

//这道题有点难，先要把数据抽象成一个图，如果两两可以连通则设距离为 1 ，不能连通设为 INF 然后分别求1,2,3,这三个点到其余点的最短路径，3个结果都加起来后，那个最小值的点理解为从这点出发，连通1,2,3三个点最短路径，也可以说是最少需要开几盏灯(这个值不会有重复计算的灯)，n-之就是答案

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 #define MAXN 205
 9 #define INF 100000000
10 
11 struct Node
12 {
13     int x,y;
14     int r;
15 }node[MAXN];
16 int G[MAXN][MAXN];  //连通关系
17 int dis[MAXN];
18 int vis[MAXN];
19 int res[MAXN];
20 
21 void dij(int n,int p)
22 {
23     for (int i=1;i<=n;i++)
24     {
25         dis[i]=G[p][i];
26         vis[i]=0;
27     }
28     dis[p]=0;
29     vis[p]=1;
30 
31     for (int i=1;i<n;i++)
32     {
33         int mp,mmm=INF;
34         for (int j=1;j<=n;j++)
35             if (!vis[j]&&dis[j]<mmm)
36             {
37                 mmm=dis[j];
38                 mp=j;
39             }
40         if (mmm==INF)
41             break;
42         vis[mp]=1;
43         for (int j=1;j<=n;j++)
44         {
45             if (!vis[j]&&dis[mp]+G[mp][j]<dis[j])
46                 dis[j]=dis[mp]+G[mp][j];
47         }
48     }
49 }
50 
51 int main()
52 {
53     int T;
54     scanf("%d",&T);
55     while(T--)
56     {
57         int n;
58         scanf("%d",&n);
59         for (int i=1;i<=n;i++)
60         {
61             int x,y,r;
62             scanf("%d%d%d",&x,&y,&r);
63             node[i]=(Node){x,y,r};
64             for (int j=1;j<=i;j++)
65             {
66                 double dist = sqrt((node[j].x-x)*(node[j].x-x)*1.0+(node[j].y-y)*(node[j].y-y)*1.0);
67                 if (dist-(node[j].r+r)<1e-5)
68                     G[i][j]=G[j][i]=1;
69                 else
70                     G[i][j]=G[j][i]=INF;
71             }
72         }
73         memset(res,0,sizeof(res));
74         dij(n,1);
75         for (int i=1;i<=n;i++)
76             res[i]+=dis[i];
77         dij(n,2);
78         for (int i=1;i<=n;i++)
79             res[i]+=dis[i];
80         dij(n,3);
81         for (int i=1;i<=n;i++)
82             res[i]=n-(res[i]+dis[i]+1);
83         int ans=-1;
84         for (int i=1;i<=n;i++)
85             ans=max(ans,res[i]);
86         printf("%d
",ans);
87     }
88     return 0;
89 }

View Code