題目描述
S 城現(xiàn)有兩座監(jiān)獄，一共關(guān)押著N 名罪犯兵琳，編號(hào)分別為1~N狂秘。他們之間的關(guān)系自然也極不和諧。很多罪犯之間甚至積怨已久躯肌，如果客觀條件具備則隨時(shí)可能爆發(fā)沖突者春。我們用“怨氣值”（一個(gè)正整數(shù)值）來(lái)表示某兩名罪犯之間的仇恨程度，怨氣值越大清女，則這兩名罪犯之間的積怨越多钱烟。如果兩名怨氣值為c 的罪犯被關(guān)押在同一監(jiān)獄，他們倆之間會(huì)發(fā)生摩擦，并造成影響力為c 的沖突事件拴袭。
每年年末读第，警察局會(huì)將本年內(nèi)監(jiān)獄中的所有沖突事件按影響力從大到小排成一個(gè)列表，然后上報(bào)到S 城Z 市長(zhǎng)那里拥刻。公務(wù)繁忙的Z 市長(zhǎng)只會(huì)去看列表中的第一個(gè)事件的影響力怜瞒，如果影響很壞，他就會(huì)考慮撤換警察局長(zhǎng)泰佳。
在詳細(xì)考察了N 名罪犯間的矛盾關(guān)系后盼砍，警察局長(zhǎng)覺(jué)得壓力巨大。他準(zhǔn)備將罪犯?jìng)冊(cè)趦勺O(jiān)獄內(nèi)重新分配逝她，以求產(chǎn)生的沖突事件影響力都較小，從而保住自己的烏紗帽睬捶。假設(shè)只要處于同一監(jiān)獄內(nèi)的某兩個(gè)罪犯間有仇恨黔宛，那么他們一定會(huì)在每年的某個(gè)時(shí)候發(fā)生摩擦。
那么擒贸，應(yīng)如何分配罪犯臀晃，才能使Z 市長(zhǎng)看到的那個(gè)沖突事件的影響力最小介劫？這個(gè)最小值是多少徽惋？
輸入輸出格式
輸入格式：
輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開。第一行為兩個(gè)正整數(shù)N 和M座韵，分別表示罪犯的數(shù)目以及存在仇恨的罪犯對(duì)數(shù)险绘。接下來(lái)的M 行每行為三個(gè)正整數(shù)aj，bj誉碴，cj宦棺，表示aj 號(hào)和bj 號(hào)罪犯之間存在仇恨，其怨氣值為cj黔帕。數(shù)據(jù)保證1<aj=<=bj<=N 代咸，0 < cj≤ 1,000,000,000，且每對(duì)罪犯組合只出現(xiàn)一次成黄。
輸出格式：
共1 行呐芥，為Z 市長(zhǎng)看到的那個(gè)沖突事件的影響力。如果本年內(nèi)監(jiān)獄中未發(fā)生任何沖突事件奋岁，請(qǐng)輸出0思瘟。
輸入輸出樣例
輸入樣例#1：4 61 4 25342 3 35121 2 283511 3 66182 4 18053 4 12884
輸出樣例#1：3512
說(shuō)明
【輸入輸出樣例說(shuō)明】罪犯之間的怨氣值如下面左圖所示，右圖所示為罪犯的分配方法厦取，市長(zhǎng)看到的沖突事件影響力是3512（由2 號(hào)和3 號(hào)罪犯引發(fā)）潮太。其他任何分法都不會(huì)比這個(gè)分法更優(yōu)。
【數(shù)據(jù)范圍】對(duì)于30%的數(shù)據(jù)有N≤ 15。對(duì)于70%的數(shù)據(jù)有N≤ 2000铡买，M≤ 50000更鲁。對(duì)于100%的數(shù)據(jù)有N≤ 20000，M≤ 100000奇钞。
這里可以用一個(gè)貪心的思想來(lái)解決這個(gè)問(wèn)題澡为，要求使怨氣最大的那一個(gè)又要最小，
那我們不妨把怨氣值排個(gè)序景埃，把怨氣值較大一對(duì)罪犯的分在兩所監(jiān)獄媒至，就這樣一直分一直分直到發(fā)生沖突（就是假設(shè)a b先被分開了，b c又被分開了谷徙，因?yàn)橹挥袃蓚€(gè)監(jiān)獄拒啰，所以a c絕對(duì)在一起，可現(xiàn)在又要分a c 了可見(jiàn)有矛盾）完慧，這時(shí)a c的怒氣值就是我們的最優(yōu)解谋旦，為什么呢？
原因很簡(jiǎn)單屈尼，因?yàn)槭前磁瓪庵祻拇蟮叫∨藕眯虻牟嶙牛珠_也是從怒氣大的慢慢分開，
還是剛剛的a b c這個(gè)例子脾歧，a b怒氣第一大甲捏，ok被分開了，兩個(gè)監(jiān)獄怒氣都沒(méi)了鞭执，b c怒氣第二大司顿，又被分開了，怒氣沒(méi)了蚕冬，現(xiàn)在a c怒氣第三大免猾，沒(méi)辦法被分開了，只能在同一個(gè)監(jiān)獄了囤热，你說(shuō)最后的解是不是a c的怒氣值猎提？
其實(shí)思路就這樣了，下面上代碼?
#include<iostream>
#include<algorithm>
using namespace std;
struct node {
int a, b, c;
}bad[100010];
int f[40010] = {}, n, m;;
void inti() {
for (int i = 1; i <= n*2; i++) {
f[i] = i;
}
return;
}//并查集初始化
int dfs(int s) {
if (f[s] == s) return s;
else {
f[s] = dfs(f[s]);
return f[s];
}
}//查找結(jié)點(diǎn)所在集合
bool cmp(node z,node t) {
return z.c > t.c;
}
int main() {
scanf("%d %d", &n, &m);
inti();
for (int i = 1; i <= m; i++) {
scanf("%d %d %d", &bad[i].a, &bad[i].b, &bad[i].c);
}
sort(bad + 1, bad + 1 + m, cmp);//按怒氣值排序
for (int i = 1; i <= m; i++) {
int ra = dfs(bad[i].a), rb = dfs(bad[i].b);
if (ra == rb) {
printf("%d", bad[i].c);
return 0;
}//如果發(fā)生沖突旁蔼，就找到了最優(yōu)解锨苏，輸出，結(jié)束程序
f[ra] = dfs(bad[i].b + n);//沒(méi)沖突棺聊，就分到不同的監(jiān)獄
f[rb] = dfs(bad[i].a + n);
}
printf("0");//沒(méi)沖突事件伞租，0，over限佩！
return 0;//結(jié)束？Ｂ阆摇！
}
感謝作喘，留下一個(gè)贊Thanks?(?ω?)?理疙！
