hdu 1879 继续畅通工程解题报告

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1879

Problem Description

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

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

本题为最小生成树的简单题；直接用Kruskal算法就好

 1  /*********   hdu 1879   ************/
 2  /*********   琴心&剑胆   ************/
 3  /*********   2011/5/20 ************/
 4 #include<stdio.h>
 5 #include<stdlib.h>
 6 #define Max 100000
 7 int p[Max];
 8 int N,h;
 9 struct Ed{
10     int x,y,v,z;
11 }e[Max];
12 
13 int Find( int x ){
14     if( p[x]!=x )
15         p[x]=Find(p[x]);
16     return p[x];
17 }
18 
19 int cmp( const void *a,const void *b ){
20         return (*(struct Ed *)a).v-(*(struct Ed *)b).v;
21 }
22 
23 int Kul(  ){
24     for( int i=1;i<=N*(N-1)/2;++i ){
25         int x=e[i].x;
26         int y=e[i].y;
27         x=Find(x);
28         y=Find(y);
29         if( x!=y ){
30             p[x]=y;
31             if( !e[i].z )
32                 h+=e[i].v;
33         }
34     }
35 }
36 int main(){
37     while( scanf( "%d",&N )!=EOF,N ){
38        for( int i=0;i<Max;++i )
39             p[i]=i;
40         for( int i=1;i<=N*(N-1)/2;++i ){
41             scanf( "%d%d%d%d",&e[i].x,&e[i].y,&e[i].v,&e[i].z );
42             if(e[i].z)
43                 p[Find(e[i].x)]=p[Find(e[i].y)];//已经有路了，就不用连了，开始就因为少了这一句一直WA
44         }
45         qsort(e+1,N*(N-1)/2,sizeof( e[0] ),cmp );
46         h=0;
47         Kul(  );
48         printf( "%d\n",h );
49     }
50 }

hdu 1879 继续畅通工程 解题报告

hdu 1879 继续畅通工程解题报告