这么他就足以因此垂直的公路从叁个农场到另贰

作者:手机购彩网站编程

★★ 输入文件:roads.in 输出文件:roads.out 简单对比
时间限制:1 s内存限制:128 MB

译 by CmYkRgB123

描述

Farmer John 刚刚得到了几个新农场!他想把这几个农场用路连接起来,这样他就可以通过笔直的公路从一个农场到另一个农场了。现在已经有了几条连接着的农场。

N (1 ≤ N ≤ 1,000) 个农场中,每个农场的位置在坐标平面的 (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     ifn=-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; 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; 62     return f[x]; 63 } 64 int unionn(int x,int y) 65 { 66     int fx=find; 67     int fy=find; 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;read; 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;read;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 }

本文由手机购彩网站发布,转载请注明来源

关键词: