NOIP2010T3 | 关押罪犯

Portal

考虑这样一个问题:是否存在一种分配罪犯的方案,使冲突事件的影响力不超过 midmid 。显然,当 midmid 较小时可行的方案对于更大的 midmid 仍然可行。换言之,本题的答案具有单调性,可以通过二分法,把求最值的问题转化为判断问题。

二分答案,设当前二分值为 midmid 。此时,任意两个仇恨程度大于 midmid 的罪犯都必须被安排在不同的监狱里。这张无向图的节点需要被分成两个集合(两个监狱),并且每个集合内部都没有边(同一个监狱内没有仇恨程度大于 midmid 的罪犯)。所有,我们用染色法判断该无向图是否为二分图即可。若是二分图,则令二分上界 r=midr=mid ,否则令下界 l=mid+1l=mid+1

Quoted from 《算法竞赛进阶指南》

本题难度?自闭了。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <queue>
#include <cstdio>
#include <cstring>
const int N=2e4+1,M=1e5+1;
int n,m,fp,hed[N],ver[M<<1],nxt[M<<1],edg[M<<1],color[N];
int read() {
int x=0;char c=getchar();
while(c<48||c>57) c=getchar();
while(c>47&&c<58) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x;
}
void link(int u,int v,int w) {
ver[++fp]=v;edg[fp]=w;nxt[fp]=hed[u];hed[u]=fp;
ver[++fp]=u;edg[fp]=w;nxt[fp]=hed[v];hed[v]=fp;
}
int dyeing(int mid) {
memset(color,0,sizeof(color));
int u,v;std::queue <int> q;
for(int s=1;s<=n;++s) {
if(color[s]) continue;
q.push(s);color[s]=1;
while(q.size()) {
u=q.front();q.pop();
for(int i=hed[u];i;i=nxt[i]) if(edg[i]>=mid)
if(!color[v=ver[i]]) q.push(v),color[v]=-color[u];
else if(color[v]==color[u]) return 0;
}
}
return 1;
}
int main() {
n=read();m=read();int l=0,r=-1,mid;
for(int i=0,u,v,w;i<m;++i) {
u=read();v=read();w=read();
link(u,v,w);r=std::max(r,w);
}++r;
while(l+1<r) {
mid=(l+r)>>1;
if(dyeing(mid)) r=mid;
else l=mid;
}
printf("%d",l);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。