HDU 1879 继续畅通工程（最小生成树）

省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

Input测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。Output每个测试用例的输出占一行，输出全省畅通需要的最低成本。Sample Input

Sample Output

3
1
0

题解：与之前的有一些变化 需要处理一下 当道路修通时，规定一节点为另一节点的父亲
　　　用自定义结构体排序再写一遍

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <vector>
 6 #include <cstdlib>
 7 #include <iomanip>
 8 #include <cmath>
 9 #include <ctime>
10 #include <map>
11 #include <set>
12 #include <queue>
13 using namespace std;
14 #define lowbit(x) (x&(-x))
15 #define max(x,y) (x>y?x:y)
16 #define min(x,y) (x<y?x:y)
17 #define MAX 100000000000000000
18 #define MOD 1000000007
19 #define pi acos(-1.0)
20 #define ei exp(1)
21 #define PI 3.141592653589793238462
22 #define INF 0x3f3f3f3f3f
23 #define mem(a) (memset(a,0,sizeof(a)))
24 typedef long long ll;
25 ll gcd(ll a,ll b){
26     return b?gcd(b,a%b):a;
27 }
28 bool cmp(int x,int y)
29 {
30     return x>y;
31 }
32 const int N=10005;
33 const int mod=1e9+7;
34 int f[N];
35 struct edge
36 {
37     int u,v,w,flag;
38     bool operator <(const edge &other)const
39     {
40         return w<other.w;
41     }
42 }a[N];
43 void init()
44 {
45     for(int i=1;i<=N;i++)
46         f[i]=i;
47 }
48 int find1(int x)
49 {
50     if(x!=f[x])
51         f[x]=find1(f[x]);
52     return f[x];
53 }
54 int main()
55 {
56     std::ios::sync_with_stdio(false);
57     int n,m;
58     while(scanf("%d",&n)&&n){
59         init();
60         m=n*(n-1)/2;
61         for(int i=0;i<m;i++){
62             scanf("%d %d %d %d",&a[i].u,&a[i].v,&a[i].w,&a[i].flag);
63             if(a[i].flag) f[a[i].u]=a[i].v;
64         }
65         sort(a,a+m);
66         int s=0;
67         for(int i=0;i<m;i++){
68             int u=a[i].u,v=a[i].v,w=a[i].w;
69             if(find1(u)==find1(v)) continue;
70             f[find1(u)]=find1(v);
71             s+=w;
72         }
73         printf("%d
",s);
74     }
75     return 0;
76 }

HDU 1879 继续畅通工程（最小生成树）

相关推荐