[POI2005]KOS-Dicing

题意翻译
描述
掷骰子是一种双人游戏，它的结果是完全随机的。最近它在整个Byteotia变得非常流行。在Byteotia的首都甚至有一个特别的掷骰子业余爱好者俱乐部。俱乐部的老主顾们花时间互相聊天并每隔一阵子就和一个随机选择的对手玩这他们最喜欢的游戏。一天中赢得最多游戏的人会得到“幸运者”头衔。有时晚上俱乐部很安静，只有很少的比赛。这是哪怕赢一场也能获得“幸运者”头衔的时间。

很久很久以前有一个很不走运的人，叫Byteasar，赢得了这个光荣的头衔。他被深深地震惊了以至于完全忘了他已经赢了多少场。现在他想知道他有多幸运，以及幸运之神是否最终会向他微笑——也许他的运气会变好？他确切地知道在那个幸运的晚上有多少场游戏以及是谁玩的。然而，他不知道结果。Byteasar希望查明至少要赢几场才能获得“幸运者”头衔。做个好人，帮他满足他的好奇心吧！

任务：写一个程序：

对于每场游戏从stdin读入这场游戏的一对玩家 找到最小的数k，使得存在一个游戏结果的集合，其中赢最多的玩家赢了k场。向stdout输出数k和找到的集合中游戏的结果

输入

stdin的第一行有一个一对由一个空格分开整数n和m (1 <= n, m <= 10000) 。n表示玩家数，m表示游戏数。玩家从1到n编号。在接下来的m行中有每场游戏的一对玩家的编号，由一个空格分开，描述了游戏的序列。一对玩家可能会在这个序列中多次出现。

输出

stdout的第一行应该包含一个确定的数k。对于在输入的第i行指定的一对玩家a, b，如果在找到的结果集合中a胜过b，则在输出的第i行输出1, 否则输出0.

输入输出样例
输入 #1复制
4 4
1 2
1 3
1 4
1 2
输出 #1复制
1
0
0
0
1

我们看到最大值最小，不难想到二分。

然后我们用到每个点到汇点的流量表示赢的场数，源点到每场比赛流量为1，代表只有一个人能赢。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e4+10,M=2e5+10,inf=0x3f3f3f3f;
int n,m,h[N],s,t,a[N>>1],b[N>>1];
int head[N],nex[M],to[M],w[M],tot;
inline void ade(int a,int b,int c){ 
   
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){ 
   
	ade(a,b,c); ade(b,a,0);
}
inline void init(int mid){ 
   
	tot=1;	memset(head,0,sizeof head);
	for(int i=1;i<=m;i++)	add(s,i,1),add(i,a[i]+m,1),add(i,b[i]+m,1);
	for(int i=1;i<=n;i++)	add(i+m,t,mid);
}
inline int bfs(){ 
   
	memset(h,0,sizeof h); queue<int> q;	q.push(s); h[s]=1;
	while(q.size()){ 
   
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){ 
   
			if(!h[to[i]]&&w[i]){ 
   
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){ 
   
	if(x==t)	return f; int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){ 
   
		if(w[i]&&h[to[i]]==h[x]+1){ 
   
			int mi=dfs(to[i],min(f,w[i]));
			w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
inline int dinic(){ 
   
	int res=0;	while(bfs()) res+=dfs(s,inf); return res;
}
inline int check(int mid){ 
   
	init(mid); return dinic()>=m;
}
int bsearch(){ 
   
	int l=1,r=1e5;
	while(l<r){ 
   
		int mid=l+r>>1;
		if(check(mid))	r=mid;
		else	l=mid+1;
	}
	check(l);
	return l;
}
signed main(){ 
   
	cin>>n>>m; t=n+m+1;
	for(int i=1;i<=m;i++)	cin>>a[i]>>b[i];
	cout<<bsearch()<<endl;
	for(int i=1;i<=m;i++){ 
   
		if(w[head[i]])	puts("1");
		else	puts("0");
	}
	return 0;
}

今天的文章[POI2005]KOS-Dicing分享到此就结束了，感谢您的阅读。