转载

HDU1879 kruscal 继续畅通工程

继续畅通工程

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 17028 Accepted Submission(s): 7319

Problem Description

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

Input

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

当N为0时输入结束。

Output

每个测试用例的输出占一行，输出全省畅通需要的最低成本。

Sample Input

3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0

Sample Output

3 1 0

Author

ZJU

Source

浙大计算机研究生复试上机考试-2008年

最基础的KRUSCAL模板问题

只不过是用结构体实现，sort排序一下即可，从最小边枚举贪心的思想

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; struct node{ int u,v,w,judge; }que[50000]; int n,cnt; bool cmp(struct node a,struct node b){   return a.w<b.w; } int father[500]; void init(){  for(int i=1;i<=n;i++)  father[i]=i; } int find(int a){  if(father[a]!=a)  father[a]=find(father[a]);  return father[a]；///不知道为什么return a；就是WA，按理说应该可以的啊，他俩不是相等的时候才返回嘛 } bool Union(int x1,int x2){  int t1=find(x1);  int t2=find(x2);  if(t1!=t2){    father[t1]=t2;    return true;  }  return false; } int kruscal(){   int sum=0;   int edge=0;   sort(que,que+cnt,cmp);   for(int i=0;i<cnt;i++){     if(Union(que[i].u,que[i].v)){     sum+=que[i].w;     edge++;     if(edge==n-1)      return sum;     }   } } int main(){  while(scanf("%d",&n)!=EOF){   if(n==0)   break;   //  memset(father,0,sizeof(father));   init();   cnt=n*(n-1)/2;   for(int i=0;i<cnt;i++){     scanf("%d%d%d%d",&que[i].u,&que[i].v,&que[i].w,&que[i].judge);     if(que[i].judge==1)     que[i].w=0;   }   printf("%d/n",kruscal());  }  return 0; }

正文到此结束