2017"百度之星"程式設計大賽 - 資格賽：1002 度度熊的王國戰略

題目：

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      

思路：看完題目各種想法，最短路、tarjin算法、dfs、并查集等等。因為可能有重邊等情況，覺得還是用并查集會快一點，沒想到在WA幾次後過了，2333~如果輸入資料不能組成一個連通塊就輸出“0”，否則就去掉最小代價的那個點（用一個數組記錄破壞每個點的所需代價）。總感覺這次比賽資料有很多問題...

CODE：

#include<bits/stdc++.h>
using namespace std;
int num[],pre[];
int Find(int x){
        return x==pre[x]?x:pre[x]=Find(pre[x]);
}
int main()
{
        int n,m,i,j,k;
        while(~scanf("%d%d",&n,&m)){
                for(i=;i<=n;i++) pre[i]=i;
                memset(num,,sizeof(num));
                k=;
                while(m--){
                        int a,b,c;
                        scanf("%d%d%d",&a,&b,&c);
                        if(a==b) continue;
                        num[a]+=c;num[b]+=c;
                        int fx=Find(a),fy=Find(b);
                        if(fx!=fy){
                                k++;
                                pre[fx]=fy;
                        }
                }
                sort(num+,num++n);
                if(k==n-) printf("%d\n",num[]);
                else puts("0");
        }
        return ;
}