Heavy Transportation
题目大意：
Hugo Heavy要从城市1到城市N运送货物，有M条道路，每条道路都有它的最大载重量，问从城市1到城市N运送最多的重量是多少。
思路：
这个题，根据题目要求，我们发现这个题和最小生成树正好相反，所以我们使用Kruskal求解最大生成树。
但这个题有一个坑，就是不需要非得搞出n-1条边，只需要能从1到达n就好了。
该题讨论。。。
这个说dog题目的讨论我给满分。
当然还是要附上代码的：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 struct hehe{ 5 int a; 6 int b; 7 int c; 8 }edge[1000010]; 9 int cmp(hehe x,hehe y){ 10 return x.c>y.c; 11 } 12 int n,m,father[1010],haha; 13 int find(int z){ 14 if(father[z]!=z) 15 father[z]=find(father[z]); 16 return father[z]; 17 } 18 int main(){ 19 scanf("%d",&haha); 20 for(int lalala=1;lalala<=haha;lalala++){ 21 scanf("%d%d",&n,&m); 22 for(int i=1;i<=m;++i){ 23 scanf("%d%d%d",&edge[i*2].a,&edge[i*2].b,&edge[i*2].c); 24 edge[i*2-1].a=edge[i*2].a; 25 edge[i*2-1].b=edge[i*2].b; 26 edge[i*2-1].c=edge[i*2].c; 27 } 28 m*=2; 29 for(int i=1;i<=n;++i) 30 father[i]=i; 31 sort(edge+1,edge+m+1,cmp); 32 int ans=-1; 33 for(int i=1;i<=m;++i){ 34 if(find(1)==find(n)) 35 break; 36 if(find(edge[i].a)!=find(edge[i].b)){ 37 ans=edge[i].c; 38 father[find(edge[i].a)]=find(edge[i].b); 39 } 40 } 41 printf("Scenario #%d: %d ",lalala,ans); 42 printf(" "); 43 } 44 return 0; 45 }