Vijos 1776 關押罪犯，vijos1776關押罪犯

Vijos 1776 關押罪犯，vijos1776關押罪犯

這道題看了網上好多的題解，用的都是二分圖的算法，但是自己卻用的是貪心加並查集的做法。二分圖的做法其實我並不會，是不是很神奇。

    實際上貪心的算法很好想，只要先用一個結構體維護兩個人的怒氣值，然後從小到大排序。再從小到大搜一遍。時間復雜度大概是（nlogn+n）總時154ms，基本上是C++中最快的了。。。。

   在搜的過程中，就需要用到並查集了。因為需要盡量把不會產生怨氣值的罪犯關在一起，所以首先維護一個名為fa的數組，記錄的是兩個監獄中所關押的犯人，在從小往大搜的過程中，假設是第i條關系，如果這條關系所連接的兩個人已經被關在同一個監獄中則為矛盾，輸出怨氣值即可，如果兩個人不在同一個監獄，那麼則進行下一步。下一步需要用到另一個數組dui，即“敵對”。假設第i條關系連接的兩個

人是a和b，那麼就需要將a和b關在兩個監獄中，該如何表示呢？就利用到了dui這個數組。dui[a] 表示會和 a 產生怒氣值的罪犯的編號。因為這個人此前肯定已經在與 a 不同的監獄中，所以就將當前，即 b 這個罪犯和dui[a]關在一起。同理，將a和dui[b]關在一起。這樣這道題就解決了。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int u,v,c;
} a[600001];
int n,m,fa[1000000];
int com(node a,node b)//比較函數 
{
    return a.c>b.c;
}
int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);//路徑壓縮 
    return fa[x];
}
void cling(int x,int y)
{
    int f1=find(x),f2=find(y);
    if(f1!=f2) fa[f1]=f2;
}
int dui[1000000];//敵對 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
      scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);
    sort(a+1,a+m+1,com);
    for(int i=1;i<=m;i++)
    fa[i]=i;//初始化 
    for(int i=1;i<=m;i++){
        int f1=find(a[i].u),f2=find(a[i].v);
        if(f1==f2){//如果矛盾則輸出答案 
           cout<<a[i].c;
           return 0;
        }
        if(dui[a[i].u]==0) dui[a[i].u]=a[i].v;//如果沒有敵對的罪犯，直接將當前罪犯添加為敵對 
        if(dui[a[i].v]==0) dui[a[i].v]=a[i].u;//同理 
        cling(dui[a[i].u],a[i].v);//將u的敵對罪犯與v關在一起 
        cling(dui[a[i].v],a[i].u);//同理 
    }
    cout<<"0";//如果始終不矛盾，則為0 
}