【2017

【链接】：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=774

【题目】：

度度熊的王国战略

Problem Description

度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。

哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。

所以这一场战争，将会十分艰难。

为了更好的进攻哗啦啦族，度度熊决定首先应该从内部瓦解哗啦啦族。

第一步就是应该使得哗啦啦族内部不能同心齐力，需要内部有间隙。

哗啦啦族一共有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;
}