P1546 最短网络(codevs | 2627村村通)

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 }