洛谷P1525 关押罪犯并查集

无冲突输出 0
洛谷P1525 关押罪犯
并查集
用拆点法将一个点拆成两份
一个点和 x 的朋友相连一个点和 x的敌人相连
若 x 与 y 是敌人
因为只有两个阵营
所以满足敌人的敌人就是朋友
然后 x 连向 y 的敌人
y 连向 x 的敌人因为这是双向边所以 y的朋友就是x的敌人就不用连了
如果某一时刻 getfather(e[ i ].from)==getfather(e[ i ].to)
这说明两个点已经是敌人关系的两个人通过朋友关系连上了那就结束了

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <iostream> 
 9 #define ll int 
10 using namespace std ; 
11 
12 const int maxn = 20011,maxm = 100011 ; 
13 ll n,m,u,v ; 
14 ll fa[2*maxn] ; 
15 struct node{
16     ll from,to,val ; 
17 }e[maxm] ; 
18 
19 inline ll read() 
20 {
21     char ch = getchar() ; 
22     ll x = 0 ,f = 1 ; 
23     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; }    
24     while(ch>='0'&&ch<='9') { x = x*10+ch - 48 ; ch = getchar() ; } 
25     return x*f ; 
26 }
27 
28 inline bool cmp(node a,node b) 
29 {
30     return a.val > b.val ; 
31 }
32 
33 inline ll getfather(int x) 
34 {
35     if(fa[x]==x) return x ; 
36     fa[ x ] = getfather(fa[ x ]) ; 
37     return fa[ x ] ;  
38 }
39 
40 int main()
41 {
42     n = read() ;  m = read() ; 
43     for(int i=1;i<=m;i++) 
44         e[ i ].from = read(),e[ i ].to = read(),e[ i ].val = read() ; 
45         
46     sort(e+1,e+m+1,cmp) ;
47     for(int i=1;i<=2*n;i++) fa[ i ] = i ; 
48     for(int i=1;i<=m;i++) 
49     {
50         u = getfather(e[ i ].from) ; 
51         v = getfather(e[ i ].to) ; 
52         if( u==v ) 
53         {
54             printf("%d
",e[ i ].val) ; 
55             return 0 ; 
56         } 
57         fa[ u ] = getfather( e[ i ].to+n ) ; // 注意这边是 fa[ getfather( e[ i ].from ) 
58         fa[ v ] = getfather( e[ i ].from+n ) ; 
59     } 
60     printf("0
") ; 
61     return 0 ; 
62 }

洛谷P1525 关押罪犯 并查集

洛谷P1525 关押罪犯并查集