【POI 2005】KOS-Dicing

传送门

---

problem

有 $n$ 个人，之间会有 $m$ 场比赛。你可以设定所有比赛的结果。你希望获胜场次最多的人获胜的场次数尽量少，请求出这个最小值，并输出方案。

数据范围：$1\le n,m\le 10000$。

---

solution

由于我们要最小化最大值，很明显的二分，假设现在二分到的值是 $\lambda$，考虑怎么 $check$。

考虑网络流。从源点 $S$ 向每个比赛连 $1$ 的边，每个比赛向对应的两个人连 $1$ 的边，然后每个人向汇点 $T$ 连 $\lambda$ 的边（相当于限制了只能胜 $\lambda$ 场）。

然后跑最大流，看最后的流量是否为 $m$（就是看 $m$ 个比赛的胜负能否分配完），调整 $\lambda$ 继续二分即可。

注意一下，最后还要 $check$ 一遍 $ans$，因为二分时最后 $check$ 到的不一定是答案。

---

code

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,tot,S,T,now;
int first[N],v[N],w[N],nxt[N];
int U[N],V[N],d[N],f[N];
void add(int x,int y,int z){
	nxt[++tot]=first[x],first[x]=tot,v[tot]=y,w[tot]=z;
}
void build(int mid){
	tot=1,memset(first,0,sizeof(first));
	for(int i=1;i<=m;++i){
		add(S,i,1),add(i,S,0);
		add(i,m+U[i],1),add(m+U[i],i,0);
		add(i,m+V[i],1),add(m+V[i],i,0);
	}
	for(int i=m+1;i<=n+m;++i)  add(i,T,mid),add(T,i,0);
}
bool bfs(int S){
	memset(d,-1,sizeof(d));
	memcpy(f,first,sizeof(f));
	queue<int>Q;Q.push(S);d[S]=0;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=f[x];i;i=nxt[i]){
			int to=v[i];
			if(w[i]&&d[to]==-1){
				d[to]=d[x]+1,Q.push(to);
			}
		}
	}
	return d[T]!=-1;
}
int dinic(int x,int flow){
	if(x==T)  return flow;
	int delta,ans=0;
	for(int &i=f[x];i;i=nxt[i]){
		int to=v[i];
		if(w[i]&&d[to]==d[x]+1){
			delta=dinic(to,min(flow,w[i]));
			w[i]-=delta,w[i^1]+=delta;
			flow-=delta,ans+=delta;
			if(!flow)  return ans;
		}
	}
	return ans;
}
bool check(int mid){
	build(mid),now=0;
	while(bfs(S))  now+=dinic(S,inf);
	return now==m;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
		scanf("%d%d",&U[i],&V[i]);
	S=0,T=n+m+1;
	int l=1,r=m;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))  r=mid;
		else  l=mid+1;
	}
	printf("%d\n",l),check(l);
	for(int i=1;i<=m;++i)
		for(int j=first[i];j;j=nxt[j])
			if(v[j]!=S&&(!w[j]))  puts(v[j]-m==U[i]?"1":"0");
	return 0;
}