【UVA 10369】 Arctic Network （最小生成树）

【题意】

　　南极有n个科研站，要把这些站用卫星或者无线电连接起来，使得任意两个都能直接或者间接相连。任意两个都有安装卫星设备的，都可以直接通过卫星通信，不管它们距离有多远。而安装有无线电设备的两个站，距离不能超过D。 D越长费用越多。

现在有s个卫星设备可以安装，还有足够多的无线电设备，求一个方案，使得费用D最少（D取决与所有用无线电通信的花费最大的那条路径）。

Input
The first line of input contains N, the number of test cases. The first line of each test case contains
1 ≤ S ≤ 100, the number of satellite channels, and S < P ≤ 500, the number of outposts. P lines
follow, giving the (x, y) coordinates of each outpost in km (coordinates are integers between 0 and
10,000).
Output
For each case, output should consist of a single line giving the minimum D required to connect the
network. Output should be specified to 2 decimal points.
Sample Input
1
2 4
0 100
0 300
0 600
150 750
Sample Output
212.13

【分析】

　　如果没有卫星设备，那就直接最小生成树。

　　如果卫星设备>=2，那么可以孤立s-1个区域出来（把卫星设备放在那里，剩下一个设备放在大集团里面）

　　相当于树的s-1条边置为0，

　　那当然是最小生成树的后s-1大的边置为0咯。

　　krukal的过程就可以直接计算结果了。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 using namespace std;
 9 #define Maxn 510
10 
11 struct node
12 {
13     int x,y;
14     double c;
15 }t[Maxn*Maxn];int len;
16 
17 int nx[Maxn],ny[Maxn];
18 
19 void ins(int x,int y,double c)
20 {
21     t[++len].x=x;t[len].y=y;t[len].c=c;
22 }
23 
24 bool cmp(node x,node y) {return x.c<y.c;}
25 
26 int fa[Maxn];
27 int ffa(int x)
28 {
29     if(x!=fa[x]) fa[x]=ffa(fa[x]);
30     return fa[x];
31 }
32 
33 int main()
34 {
35     int T;
36     scanf("%d",&T);
37     while(T--)
38     {
39         int s,p;
40         scanf("%d%d",&s,&p);
41         for(int i=1;i<=p;i++) scanf("%d%d",&nx[i],&ny[i]);
42         len=0;
43         for(int i=1;i<=p;i++)
44          for(int j=i+1;j<=p;j++)
45          {
46              double xx=(double)(nx[i]-nx[j]),yy=(double)(ny[i]-ny[j]);
47              ins(i,j,sqrt(xx*xx+yy*yy));
48          }
49         sort(t+1,t+1+len,cmp);
50         int cnt=0;
51         for(int i=1;i<=p;i++) fa[i]=i;
52         if(p==s) printf("0.00
");
53         else
54         {
55             for(int i=1;i<=len;i++)
56             {
57                 if(ffa(t[i].x)!=ffa(t[i].y))
58                 {
59                     fa[ffa(t[i].x)]=ffa(t[i].y);
60                     cnt++;
61                     if(cnt==p-s) {printf("%.2lf
",t[i].c);break;}
62                 }
63             }
64         }
65         
66     }
67     return 0; 
68 }

View Code

2016-11-01 16:35:05