★★ 输入文件:roads.in
输出文件:roads.out
简单对比
时间限制:1 s 内存限制:128 MB
译 by CmYkRgB123 描述 Farmer John 刚刚得到了几个新农场!他想把这几个农场用路连接起来,这样他就可以通过笔直的公路从一个农场到另一个农场了。现在已经有了几条连接着的农场。 N (1 ≤ N ≤ 1,000) 个农场中,每个农场的位置在坐标平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已经有 M (1 ≤ M ≤ 1,000) 条路以前就被建好了。请你帮助 Farmer John 考虑建设尽量少长度的额外的路,使他的农场连在一起。 输入 * 第 1 行: 两个整数: N , M * 第 2..N+1 行: 两个整数 Xi , Yi * 第 N+2..N+M+2 行: 两个整数: i , j, 表示已经存在从农场i到农场j的路。 输出 * 第 1 行: 额外的路的最少长度,保留2小数。 请使用 64 位的浮点数。 样例输入 4 1 1 1 3 1 2 3 4 3 1 4 样例输出 4.00
好久没写最小生成树了结果爆了一堆bug。。
对于已经建造的道路,我们可以把它的权值设置成0
然后跑裸地kruskal
注意内存限制!!!!!!!!!!!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #define INF 0x7ffff
7 using namespace std;
8 const int MAXN=1001;
9 int vis[MAXN][MAXN];// 记录两个城市之间是否已经有道路相连
10 double dis[MAXN][MAXN];
11 struct node
12 {
13 int u,v,nxt;
14 double w;
15 }edge[1000001];
16 int f[MAXN*3];
17 int num=1;
18 struct pos
19 {
20 long long int x,y;
21 }where[MAXN*3];
22 int n,m;
23 double ans=0;
24 int read(int & n)
25 {
26 int flag=0,x=0;char c='/';
27 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
28 while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
29 if(flag)n=-x;
30 else n=x;
31 }
32 void deal_dis()
33 {
34 //for(int i=1;i<=n;i++)
35 // for(int j=1;j<i;j++)
36 // dis[i][j]=INF;
37
38 for(int i=1;i<=n;i++)
39 for(int j=1;j<i;j++)
40 dis[i][j]=sqrt((where[i].x-where[j].x)*(where[i].x-where[j].x)+(where[i].y-where[j].y)*(where[i].y-where[j].y));
41
42 /*for(int i=1;i<=n;i++)
43 {
44 for(int j=1;j<i;j++)
45 printf("%.2lf ",dis[i][j]);
46 printf("\n");
47 }*/
48 //cout<<dis[219][65];
49 }
50 void add_edge(int p,int q,double we)
51 {
52 edge[num].u=p;
53 edge[num].v=q;
54 edge[num].w=we;
55 // cout<<edge[num].w<<endl;
56 num++;
57 }
58 int find(int x)
59 {
60 if(f[x]!=x)
61 f[x]=find(f[x]);
62 return f[x];
63 }
64 int unionn(int x,int y)
65 {
66 int fx=find(x);
67 int fy=find(y);
68 f[fx]=fy;
69 }
70 int comp(const node & a,const node & b)
71 {
72 return a.w<b.w;
73 }
74 void kruskal()
75 {
76 sort(edge+1,edge+num+1,comp);
77 int k=1;
78 for(int i=1;i<=num;i++)
79 {
80 if(find(edge[i].u)!=find(edge[i].v))
81 {
82 unionn(edge[i].u,edge[i].v);
83 k++;
84 ans=ans+edge[i].w;
85 }
86 if(k==n)
87 break;
88 }
89 printf("%.2lf",ans);
90 }
91 int main()
92 {
93 freopen("roads.in","r",stdin);
94 freopen("roads.out","w",stdout);
95 read(n);read(m);
96 for(int i=1;i<=n;i++)
97 cin>>where[i].x>>where[i].y,f[i]=i;
98
99 for(int i=1;i<=m;i++)
100 {
101 int x,y;
102 read(x);read(y);
103 add_edge(x,y,0.00);
104 vis[x][y]=1;
105 }
106
107 deal_dis();
108
109 for(int i=1;i<=n;i++)
110 for(int j=1;j<i;j++)
111 if(i!=j&&vis[i][j]==0)
112 add_edge(i,j,dis[i][j]);
113
114 kruskal();
115 return 0;
116 }