## poj2377

2012年08月02日 ⁄ 综合 ⁄ 共 1114字 ⁄ 字号 评论关闭

http://poj.org/problem?id=2377

` 1 #include<stdio.h> 2 #include<algorithm> 3  using namespace std; 4 struct line 5 { 6     int begin; 7     int end; 8     int lenth; 9 };10 line * amount;11 int * father;12 int numofnode,numofline;13 int i,j,a,b,c;14 int minlen;15 int find(int k)16 {17     return father[k]==k?k:father[k]=find(father[k]);18 }19 int cmp(line a,line b)20 {21     return a.lenth>b.lenth?1:0;22 }23 void ini()24 {25     scanf("%d %d",&numofnode,&numofline);26     father=new int [numofline+1];27     amount=new line [numofline];28     for(i=1;i<=numofnode;i++) father[i]=i;29     for(i=0;i<numofline;i++)30     {31         scanf("%d %d %d",&a,&b,&c);32         amount[i].begin=a;33         amount[i].end=b;34         amount[i].lenth=c;35     }36     sort(amount,amount+numofline,cmp);37 }38 int kruskal()39 {40     minlen=0;41     int counter=0;42     for(i=0;i<numofline;i++)43     {44         a=find(amount[i].begin),b=find(amount[i].end);45         if(a!=b)46         {47             father[a]=b;48             minlen+=amount[i].lenth;49             counter++;50         }51     }52     return counter;53 }54 void pr()55 {56     int k=kruskal();57     if(k<numofnode-1) printf("-1\n");58     else printf("%d\n",minlen);59     delete [] father;60     delete [] amount;61 }62 int main()63 {64     ini();65     pr();66     return 0;67 }`