P1546 最短网络 Agri-Net
P1991 有线通讯网
题目背景
老乡约翰(John)被选为他们镇的村长！他里面一个竞选承诺就是在镇上建立起互联网，并接连到所有的农场。当然，他索要您的扶持。
问题叙述
国防部安排用有线网络连接若干个边防哨所。2
种分歧的电视发表技术用于搭建有线网络；
种种边防哨所都要配备有线电收发器；有一些观看哨还足以增配卫星电话。
随意七个布局了一条卫星电话线路的哨所（两边都ᤕ有卫星电话）均能够打电话，无论
她俩距离多少距离。而只经过有线电收发器通话的哨所之间的距离不可能超越D，那是受收发器
的功率范围。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。
收发器要求联合采购和设置，所以总体哨所只好选用设置一种型号的收发器。换句话
说，每一对哨所之间的打电话距离都是同一个
D。你的职分是确定收发器必须的微乎其微通话距
离 D，使得每一对哨所之间起码有一条通话路径（直接的或者直接的）。
问题叙述
约翰(John)已经给她的农场配备了一条高效的网络线路，他想把那条路线共享给其余农场。为了用很小的消费，他想铺设最短的光纤去老是所有的农场。
您将获得一份各农场之间延续成本的列表，你不可以不找出能连续所有农场并所用光纤最短的方案。每三个农场间的距离不会超过100000
输入输出格式
输入格式：
从 wireless.in 中输入数据第 1 行，2 个整数 S 和 P，S
表示可设置的卫星电话的哨所
数，P 代表边防哨所的多少。接下里 P 行，每行八个整数 x，y
描述一个观看哨的平面坐标
(x, y)，以 km 为单位。
出口格式：
输出 wireless.out 中
第 1 行，1 个实数
D，表示无线电收发器的细微传输距离，㋮确到小数点后两位。
输入输出格式
输入格式：
首先行： 农场的个数，N（3<=N<=100）。
其次行..结尾:
后来的行包涵了一个N*N的矩阵,表示每个农场里头的相距。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，由此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有路经从第i个农场到它自己。
输出格式：
唯有一个出口，其中涵盖连接到各个农场的光纤的细小长度。
输入输出样例
输入样例#1：
2 4
0 100
0 300
0 600
150 750
出口样例#1：
212.13
输入输出样例
输入样例#1：
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出样例#1：
28
说明
附送样例一个
对于 20% 的数据：P = 2，S = 1
对此其它 20% 的数据：P = 4，S = 2
对此 100% 的数码保险：1 ≤ S ≤ 100，S < P ≤ 500，0 ≤ x，y ≤ 10000。
krustra，建n-s条边即可
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<cmath>
5 using namespace std;
6
7 struct Edge{
8 int u,v;
9 double w;
10 }e[250100];
11 int far[510];
12 int x[510],y[510];
13 int n,s,cnt,p;
14 double ans;
15 int find(int a)
16 {
17 return far[a]==a?a:far[a]=find(far[a]);
18 }
19 bool cmp(Edge a,Edge b)
20 {
21 return a.w < b.w;
22 }
23 int main()
24 {
25 scanf("%d%d",&s,&n);
26 for(int i=1;i<=n;++i) far[i] = i;
27 for (int i=1; i<=n; ++i)
28 scanf("%d%d",&x[i],&y[i]);
29 for (int i=1; i<=n; ++i)
30 for (int j=i+1; j<=n; ++j)
31 {
32 double w = (double)sqrt((double)abs(x[i]-x[j])*abs(x[i]-x[j])+(double)abs(y[i]-y[j])*abs(y[i]-y[j]));
33 ++cnt;
34 e[cnt].u = i;
35 e[cnt].v = j;
36 e[cnt].w = w;
37 }
38 sort(e+1,e+cnt+1,cmp);
39 for(int i=1;i<=cnt;++i)
40 {
41 int a = find(e[i].u);
42 int b = find(e[i].v);
43 if(a!=b)
44 {
45 p++;
46 far[a] = b;
47 ans = e[i].w;
48 if(p==n-s) break;
49 }
50 }
51 printf("%.2lf",ans);
52 return 0;
53 }
说明
问题翻译来自NOCOW。
USACO Training Section 3.1
思路：Krukal算法;
1 #include<iostream>
2 using namespace std;
3 #define N 10010
4 #include<algorithm>
5 struct point
6 {
7 int a,b,l;
8 }farm[N];
9 int n,k;
10 int top;
11 int sum;
12 int far[N];
13 bool cmp(point a,point b)
14 {
15 return a.l<b.l;
16 }
17 int find(int a)
18 {
19 if(far[a]!=a)far[a]=find(far[a]);
20 return far[a];
21 }
22 int main()
23 {
24 cin>>n;
25 for(int i=1;i<=n;++i)
26 for(int j=1;j<=n;++j)
27 {
28 int x;
29 cin>>x;
30 if(x!=0)
31 {
32 top++;
33 farm[top].a=i;farm[top].b=j;farm[top].l=x;
34 }
35 }
36 for(int i=1;i<=n;++i)far[i]=i;
37 sort(farm+1,farm+top+1,cmp);
38 for(int i=1;i<=top;++i)
39 {
40 int aa=find(farm[i].a);
41 int bb=find(farm[i].b);
42 if(aa!=bb)
43 {
44 far[aa]=bb;
45 sum+=farm[i].l;
46 ++k;
47 }
48 if(k==n-1)break;
49 }
50 cout<<sum;
51 return 0;
52 }