洛谷3425 【POI2005】KOS-Dicing（最大流+二分）

传送门

【题目分析】

真的跪了qwq。。。为什么数组开小他竟然TLE。。。。我还以为是代码问题呢结果。。。。（很脏的话）

既然题目都要求你去找最多的最少，那肯定是二分答案了。

关键在于怎么进行check。

假设我们现在二分出一个x表示赢的最多的赢了x次，那么我们像所有玩家连一条容量为x的边对赢的次数的限制，每场比赛的两个人向这场比赛连容量为1的边，比赛向汇点连容量为1的边，这样就限制了一场比赛只会有一个人得1分。

然后就跑最大流分配比赛得分，如果最后得分=比赛数，说明所有比赛可以分配完，那么就把x向下调，否则上调。

至于方案就看比赛与两个玩家的连边哪一条没流了的（反向边就流了）。

记得每次二分如果可行都要更新一下！然后可以每次直接重构整个图，或者再开两个数组，一个记不加容量x边的head,一个记w，每次直接memcpy就行了。

【代码~】

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+10;
const int MAXM=1e5+10;
const int INF=0x3f3f3f3f;

int n,m,cnt,s,t,last;
int ans[MAXN];
int a[MAXN],b[MAXN];
int head[MAXN],cur[MAXN],depth[MAXN];
int nxt[MAXM],to[MAXM],w[MAXM];

int Read(){
	int i=0,f=1;
	char c;
	for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
	if(c=='-')
	  f=-1,c=getchar();
	for(;c>='0'&&c<='9';c=getchar())
	  i=(i<<3)+(i<<1)+c-'0';
	return i*f;
}

void Add(int x,int y,int z){
	nxt[cnt]=head[x];
	head[x]=cnt;
	to[cnt]=y;
	w[cnt]=z;
	cnt++;
}

void add(int x,int y,int z){
	Add(x,y,z);
	Add(y,x,0);
}

int bfs(){
	queue<int> q;
	memset(depth,0,sizeof(depth));
	depth[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=nxt[i]){
			int v=to[i];
			if(!depth[v]&&w[i]){
				depth[v]=depth[u]+1;
				q.push(v);
				if(v==t)
				  return 1;
			}
		}
	}
	return 0;
}

int dfs(int u,int flow){
	if(u==t)
	  return flow;
	int res=0,di,v;
	for(int &i=cur[u];i!=-1;i=nxt[i]){
		v=to[i];
		if(depth[v]==depth[u]+1&&w[i]){
			di=dfs(v,min(w[i],flow));
			if(di){
				w[i]-=di;
				w[i^1]+=di;
				res+=di;
				if(res==flow)
				  break;
			}
		}
	}
	return res;
}

int dinic(){
	int ret=0;
	while(bfs()){
		memcpy(cur,head,sizeof(head));
		ret+=dfs(s,INF);
	}
	return ret;
}

void build(int x){
	cnt=0;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;++i){
		add(a[i],i+n,1);
		add(b[i],i+n,1);
		add(i+n,t,1);
	}
	for(int i=1;i<=n;++i)
	  add(s,i,x);
}

int check(int x){
	build(x);
	return dinic()==m;
}

void update(){
	int v;
	for(int u=1;u<=m;++u){
		for(int i=head[u+n];i!=-1;i=nxt[i]){
			v=to[i];
			if(v<=n&&v!=s&&w[i]){
				if(v==a[u])
				  ans[u]=1;
				else
				  ans[u]=0;
			}
		}
	}
}

int main(){
	memset(head,-1,sizeof(head));
	n=Read(),m=Read();
	s=0,t=n+m+1;
	for(int i=1;i<=m;++i){
		a[i]=Read(),b[i]=Read();
	}
	int l=1,r=m,mid;
	while(l<=r){
		mid=l+r>>1;
		if(check(mid))
		  last=mid,r=mid-1,update();
		else
		  l=mid+1;
	}
	cout<<last<<'\n';
	for(int i=1;i<=m;++i)
	  cout<<ans[i]<<'\n';
	return 0;
}