151. [USACO Dec07] 建造路径

★★   输入文件: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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 硬币排成线题目分析代码

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人获胜。

742
来自专栏数据结构与算法

树上莫队算法

1413
来自专栏清墨_iOS分享

OpenGLES-04 绘制带颜色的立方体

前面几篇文章都只是绘制了平面图形,接下来我们开始绘制一个真正的3D立方体图形。代码在前一篇文章基础上修改。 绘制立方体之前,我们需要知道这个立方体的各个顶点坐...

3999
来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

35210
来自专栏数据结构与算法

牛客NOIP提高组(二)题解

好难啊,$30$分的枚举颜色dp应该比较好想把,$f[i][j]$表示第$i$个位置,填了$j$个颜色,然后先枚举一下$1$的颜色,前缀和优化一下,$O(n a...

1091
来自专栏章鱼的慢慢技术路

2013年第四届蓝桥杯C/C++B组省赛题目解析

2333
来自专栏数据结构与算法

2018.7.21NOIP模拟赛?解题报告

那么我们还需要对每个已经加入的右括号维护一个小根堆。每次判断是否替换掉更小的会更优

825
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

3427
来自专栏数据结构与算法

洛谷P1333 瑞瑞的木棍(欧拉回路)

题目描述 瑞瑞有一堆的玩具木棍,每根木棍的两端分别被染上了某种颜色,现在他突然有了一个想法,想要把这些木棍连在一起拼成一条线,并且使得木棍与木棍相接触的两端颜色...

3466
来自专栏数据结构与算法

P1993 小 K 的农场

题目描述 小 K 在 Minecraft 里面建立很多很多的农场,总共 n 个,以至于他自己都忘记了每个 农场中种植作物的具体数量了,他只记得一些含糊的信息(共...

32610

扫码关注云+社区

领取腾讯云代金券