問題傳送門
問題描述
S城現有兩座監獄，一共關押著N名罪犯，編號分別為1-N。他們之間的關系自然也極不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則隨時可能爆發沖突。我們用“怨氣值”（一個正整數值）來表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為cc 的罪犯被關押在同一監獄，他們倆之間會發生摩擦，并造成影響力為c c的沖突事件。

每年年末，警察局會將本年內監獄中的所有沖突事件按影響力從大到小排成一個列表，然后上報到S 城Z 市長那里。公務繁忙的Z 市長只會去看列表中的第一個事件的影響力，如果影響很壞，他就會考慮撤換警察局長。

在詳細考察了N 名罪犯間的矛盾關系后，警察局長覺得壓力巨大。他準備將罪犯們在兩座監獄內重新分配，以求產生的沖突事件影響力都較小，從而保住自己的烏紗帽。假設只要處于同一監獄內的某兩個罪犯間有仇恨，那么他們一定會在每年的某個時候發生摩擦。

那么，應如何分配罪犯，才能使Z 市長看到的那個沖突事件的影響力最小？這個最小值是多少？

輸入格式
每行中兩個數之間用一個空格隔開。第一行為兩個正整數N,M，分別表示罪犯的數目以及存在仇恨的罪犯對數。接下來的MM行每行為三個正整數aj,bj,cj，表示aj號和bj 號罪犯之間存在仇恨，其怨氣值為cj 。數據保證1<aj≤bj≤N ,0 < cj≤ 1,000,000,000，且每對罪犯組合只出現一次。
輸出格式
共1 行，為Z 市長看到的那個沖突事件的影響力。如果本年內監獄中未發生任何沖突事件，請輸出0。

輸入樣例
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

輸出樣例
3512

分析
不得不說這道題確實是一道好題，但是目前也只是知道這題是用并查集補集做的，具體講解來日再補。

代碼如下

#include <iostream> #include <algorithm> using namespace std; const int maxn=20005; struct Edge{int a,b,v; }re[amxn*5]; int p[maxn*2];bool cmp(const Edge A,const Edge B) {return A.v>B.v; } int Find(int x) {return p[x]==x?x:p[x]=Find(p[x]); } void Merge(int a,int b) {p[Find(b)]=Find(a); } int main() {ios::sync_with_stdio(false);cin.tie(0);int n,m;cin>>n>>m;for(int i=0;i<=n*2;i++)p[i]=i;for(int i=0;i<m;i++)cin>>re[i].a>>re[i].b>>re[i].v;sort(re,re+m,cmp);for(int i=0;i<m;i++){int tx=Find(re[i].a);int ty=Find(re[i].b);if(tx==ty){cout<<re[i].v<<endl;return 0;}//精髓在此Merge(re[i].a,re[i].b+n);Merge(re[i].b,re[i].a+n);}cout<<"0"<<endl;return 0; }

總結

以上是生活随笔為你收集整理的P1525关押罪犯（并查集补集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。