題目：洛谷P1525、Vijos P1776、codevs1069。

題目大意：有一些罪犯，兩個罪犯之間可能會發(fā)生沖突，沖突有個影響力，而如果兩個罪犯在不同監(jiān)獄里，就可以避免沖突?，F(xiàn)在有兩個監(jiān)獄，要你安排一種關(guān)押罪犯的方式，使得影響力最大的一次沖突影響力最小。

解題思路：貪心+并查集。先將所有沖突按影響力從大到小排序，然后一件一件處理，用并查集儲存哪些罪犯處于同一個監(jiān)獄中。我們把每個罪犯變成兩個，如果該罪犯原來編號為$i$，那么現(xiàn)在編號為$2i$和$2i-1$，如果$2i$和$2j-1$處于同一個并查集內(nèi)，則說明$i$和$j$關(guān)在不同的監(jiān)獄里。如果兩個罪犯已經(jīng)在同一監(jiān)獄里，則根據(jù)貪心的原則，該影響力就是答案。

注意題目說的如果沒有沖突，輸出0。

注意代碼第24行和25行的合并操作。

C++ Code：

?

#include<cstdio> #include<algorithm> using namespace std; int n,m; struct edge{int u,v,dis;bool operator <(const edge&rhs)const{return dis>rhs.dis;} }e[100005]; int fa[40004]; int dad(int x){return x==fa[x]?x:fa[x]=dad(fa[x]); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;++i)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].dis);sort(e+1,e+m+1);for(int i=1;i<=2*n;++i)fa[i]=i;for(int i=1;i<=m;++i){int x=dad(2*e[i].u),y=dad(2*e[i].v);if(x==y){printf("%d\n",e[i].dis);return 0;}fa[dad(2*e[i].u-1)]=y;fa[x]=dad(e[i].v*2-1);}puts("0");return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Mrsrz/p/7249653.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的[NOIP2010提高组]关押罪犯的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。