【NOIP2010】【codevs1069】关押罪犯（并查集补集，拆点）

problem

• 有n个罪犯和m对关系(表示两个罪犯的怨气值)
• 有2座监狱分别关押他们，当2个罪犯在同一个监狱时怒气值就会爆发。
• 如何分配让所有产生的怨气值中最大的怨气值最小，输出该怨气值。

solution

• 将每个点x拆成两个：x和x+n（分别表示与x同一个监狱的，与x不同监狱的）
• 将怨气关系从大到小排序，对于未分配的，将他们分配到不同监狱。即合并(x,x+n).
• 直到遇到第一个在同一个监狱的值，输出并结束程序。

codes

//并查集及补集
//凡是与i+n节点在同一个集合里的，都是不能与i在同一个集合里的。
#include<iostream>
#include<algorithm>
using namespace std;
struct Edge{ int u, v, w; }e[100010];
bool cmp(Edge a, Edge b){ return a.w>b.w; }
int fa[20010<<1];
void init(int n){ for(int i = 1; i <= n; i++)fa[i]=i; }
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
void merge(int x, int y){ x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= m; i++)
        cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+m+1,cmp);
    init(n<<1);
    for(int i = 1; i <= m; i++){
        int u = e[i].u, v = e[i].v;
        if(find(u) == find(v)){
            cout<<e[i].w<<"\n";  return 0;
        }
        merge(u+n, v);
        merge(v+n, u);
    }
    cout<<0<<"\n";//....
    return 0;
}
  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80444308