HDOJ1863 ( 畅通工程 ) 【最小生成树,kruscal】

简介:
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
复制代码
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 101
 6 typedef struct{
 7     int x,y;
 8     int len;
 9 }EDGE;
10 int set[N],n,r;
11 EDGE edge[N*N];
12 int cmp(const EDGE& a,EDGE& b)
13 {
14     return a.len<b.len;
15 }
16 void MergeSet(int a,int b)
17 {
18     int i;
19     for (i=1;i<=n;i++)
20         if(set[i]==a)
21             set[i]=b;
22 }
23 int main()
24 {
25     int i,p,sum,f,t;
26     while (scanf("%d",&r),r)//n为村庄个数
27     {
28         scanf("%d",&n);
29         //初始化set
30         for (i=1;i<=n;i++)    set[i]=i;
31         //读取边数
32         for (i=0;i<r;i++)    scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].len);
33         //已经选取的点的个数
34         p=0;
35         //路径总长度
36         sum=0;
37         //对边进行排序
38         sort(edge,edge+i,cmp);
39         for (i=0;i<r&&p!=n-1;i++)
40         {
41             //查找当前边的起始点是否在同一个集合中
42             f=set[edge[i].x];
43             t=set[edge[i].y];
44             if(f!=t)
45             {
46                 MergeSet(f,t);
47                 p++;
48                 sum+=edge[i].len;
49             }
50         }
51         if(p!=n-1)
52             printf("?\n");
53         else
54             printf("%d\n",sum);
55     }
56     return 0;
57 }
复制代码

 

本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/05/13/2498590.html,如需转载请自行联系原作者

相关文章
|
8月前
|
算法 测试技术
畅通工程 (最小生成树)
畅通工程 (最小生成树)
33 0
2021杭电多校第三场-Road Discount-wqs二分+最小生成树
get函数是求出将黑色的边权加上一个值x之后的一个花费,我们会这个函数处理出x=-1000->1000的所有情况,然后将信息储存在save中,然后在询问的时候,直接遍历save集合,遇见满足情况的便直接输出,否则输出-1,虽然没有-1的情况/doge
123 0
2021杭电多校第三场-Road Discount-wqs二分+最小生成树
|
人工智能 BI
UPC窃贼与火柴——贪心
题目描述 一个窃贼进入了火柴仓库,想要偷尽可能多的火柴。仓库里有m个集装箱,第i个集装箱里有ai个火柴盒,每个火柴盒里有bi根火柴。所有火柴盒大小相同。窃贼的帆布背包恰能容纳n个火柴盒。你的任务是找出窃贼能拿走的火柴的最大数量。他没时间重新调整火柴盒中的火柴,这就是他只是挑选不超过n个其包含火柴数之和最大的火柴盒的原因
94 0
|
人工智能 算法
HDOJ2063过山车 匈牙利算法
HDOJ2063过山车 匈牙利算法
93 0
HDOJ 1285 确定比赛名次(拓扑排序)
HDOJ 1285 确定比赛名次(拓扑排序)
123 0
|
Java
HDOJ/HDU 5686 Problem B(斐波拉契+大数~)
HDOJ/HDU 5686 Problem B(斐波拉契+大数~)
83 0