关押罪犯洛谷P1525

题目+评测传送门

思路

其实这一题有2种不同的思路,但是由于我实在是太蒟蒻了,只会其中一种,另一种看了半天都不知道它在讲什么/(ㄒoㄒ)/~~

首先,我们要学习一下二分图及其判断方法博客,然后这个题目就很好解决了,我们二分计算仇恨值,然后在如果2人仇恨值大于mid,我们就把他们相连,然后判断这个图是否是二分图,即在左右部分里面"没有冲突",而判断是否是二分图的方法,上面给的链接里面也讲了,然后这道题就OK啦

代码

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for(register int i=a;i<=b;i++)
 3 #define ll long long
 4 #define gc getchar();
 5 using namespace std;
 6 int n,m,maxx=0,num=0,ans;
 7 int head[20000+10];
 8 int colo[20000+10];
 9 struct s1
10 {
11     int fm,to,vl,nt;
12 }a[2*100000+10];
13 int scan()
14 {
15     int as=0,f=1;char c=gc;
16     while(c>'9'||c<'0'){if(c=='-') f=-1;c=gc};
17     while(c>='0'&&c<='9') {as=(as<<3)+(as<<1)+c-'0';c=gc};
18     return as*f;
19 }
20 void ad(int fm,int to,int vl)
21 {
22     a[++num].nt=head[fm];
23     a[num].fm=fm;a[num].to=to;a[num].vl=vl;
24     head[fm]=num;
25 }
26 bool chek(int mid)
27 {
28     memset(colo,0,sizeof(colo));
29     queue <int> q;
30     FOR(i,1,n)
31     {
32         if(colo[i]) continue;
33         q.push(i);colo[i]=1;//如果没有进入,随便进入一个坑,反正之前的都
34 //已经解决完了
35         while(!q.empty())
36         {
37             int u=q.front(); q.pop();
38             for(int j=head[u];j;j=a[j].nt)
39             {
40                 if(a[j].vl>=mid)
41                 {
42                     if(colo[a[j].to]==0)
43                     {
44                         colo[a[j].to]=colo[u]==1?2:1;//对立面的颜色
45                         q.push(a[j].to);
46                     }
47                     else if(colo[a[j].to]==colo[u]) return false;
48                 }
49             }    
50         }
51     }
52     return true;
53 }
54 int main()
55 {
56     n=scan();m=scan();
57     FOR(i,1,m)
58     {
59         int f,t,v;
60         f=scan();t=scan();v=scan();
61         maxx=max(v,maxx);
62         ad(f,t,v);ad(t,f,v);
63     }
64     int l=0,r=maxx+1;
65     while(l+1<r)
66     {
67         int mid=(l+r)>>1;
68         if(chek(mid)) r=mid;
69         else l=mid;
70     }
71     cout<<l;
72     return 0;
73 }