【链接】：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=774
【题目】：
度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。
哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。
所以这一场战争，将会十分艰难。
为了更好的进攻哗啦啦族，度度熊决定首先应该从内部瓦解哗啦啦族。
第一步就是应该使得哗啦啦族内部不能同心齐力，需要内部有间隙。
哗啦啦族一共有n个将领，他们一共有m个强关系，摧毁每一个强关系都需要一定的代价。
现在度度熊命令你需要摧毁一些强关系，使得内部的将领，不能通过这些强关系，连成一个完整的连通块，以保证战争的顺利进行。
请问最少应该付出多少的代价。
Input本题包含若干组测试数据。
第一行两个整数n，m，表示有n个将领，m个关系。
接下来m行，每行三个整数u,v,w。表示u将领和v将领之间存在一个强关系，摧毁这个强关系需要代价w
数据范围：
2<=n<=3000
1<=m<=100000
1<=u,v<=n
1<=w<=1000
Output对于每组测试数据，输出最小需要的代价。
Sample Input 2 1 1 2 1 3 3 1 2 5 1 2 4 2 3 3 Sample Output 1 3 【思路】模板题，用并查集判断一下联通条件就可以了。【代码】：
/* *********************************************** Author :herongwei Created Time :Sat 5 Aug 2017 17:50:23 PM CST File Name :1002.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; typedef long long LL; const int maxn = 3333; const int MOD = 1e9+7; const LL inf = 0x3f3f3f3f; const double eps= 1e-8; const double pi = acos(-1.0); int n,m,t,tot,cnt,ret,ans,tmp; inline int read() { int c=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar(); } while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} return c*f; } int fa[maxn],du[maxn]; int find(int x)// { if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void init() { for(int i=1; i<=n; ++i) fa[i]=i,du[i]=0; } int main() { //freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { init(); tot=0;//不连通 for(int i=1; i<=m; ++i) { int u,v,w; u=read();v=read();w=read(); if(u==v) continue; du[u]+=w; du[v]+=w; if(find(u)!=find(v)) { ++tot; // fa[u]=fa[v]; fa[find(u)]=find(v); } } if(tot!=n-1)//图本身不连通 { puts("0"); continue; } ret=du[1]; for(int i=2; i<=n; ++i) ret=min(du[i],ret); printf("%d\n",ret); } return 0; }
