自动搬运

查看原文

来自洛谷，原作者为

	MSqwq 一事无成的废物

搬运于2025-08-24 21:48:53，当前版本为作者最后更新于2021-07-23 10:06:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置芝士：网络流

比较好的一道网络流题了，比较适合来练习思维和构图能力，还是老生常谈的一句话：图论的题就是构图 $+$ 跑板子
首先最难的一步，画出源点和汇点这里用 st 和 en 表示 好然后我们考虑将起点和每一场比赛连线，容量为 1，这个的意思就是每个比赛最多有一个人获胜，这里用粉色表示，因为粉色好康
然后将每一场比赛和相对应的两个人连线，容量为 1，代表这个人获胜或者是不获胜，这里用绿色表示
然后将所有人和终点连线
那么问题来了，容量为多少呢？
这个值我们不确定对吧，表示的是胜场的场数，所以我们要去枚举，怎么枚举呢 $1-n$ 依次枚举？那岂不直接上天。很容易可以发现这个其中是有单调性的，如果给的容量越大，那么胜场就会相应的变大，所以我们考虑二分答案，好像 二分答案 $+$ 网络流 已经成固定套路了
此题有可能还过不了，可能会 T 掉，所以简单的再观察亿下，可以发现，我们画的是二分图，所以曾广路会很短，所以我们可以缩小退出 $dfs$ 当然如果你用的是 $dinic$ 就当我没说啦，因为是到源点的距离，所以也无所谓啦，我这种只是提醒使用 $ISAP$ 的同学qwq
然后就轻松的解决了这一题啦，代码也就很简单了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
const int N=300010,M=80000010;
struct MS{
	int from,to,next,z;
}e[M];
int elast[N],cur[N],k=1;
void print(int x,int y,int z){cout<<x<<"->"<<y<<"="<<z<<endl;}
void add(int x,int y,int z)
{
	//print(x,y,z);
	e[++k].to=y,e[k].from=x,e[k].z=z,e[k].next=elast[x],elast[x]=k;
	e[++k].to=x,e[k].from=y,e[k].z=0,e[k].next=elast[y],elast[y]=k;
}
struct MSQWQ{
	int x,y;
}a[N];
int n,m;
int ans;
int st,en;
int dis[N],cnt[N];
void bfs(int en)
{
	queue<int>q;
	q.push(en);
	for(int i=0;i<=N-10;i++)cur[i]=elast[i],dis[i]=-1,cnt[i]=0;
	dis[en]=0;
	cnt[0]=1;
	while(!q.empty())
	{
		int now=q.front();q.pop();
		for(int i=elast[now];i;i=e[i].next)
		{
			int to=e[i].to;
			if(dis[to]==-1)
			{
				dis[to]=dis[now]+1;
				cnt[dis[to]]++;
				q.push(to);
			}
		}
	}
}
int dfs(int x,int flow)
{
	if(x==en)return flow;
	int d=0;
	for(int i=cur[x];i;i=e[i].next)
	{
		cur[x]=i;
		int to=e[i].to;
		if(e[i].z>0&&dis[x]==dis[to]+1)
		{
			int tmp=dfs(to,min(e[i].z,flow-d));
			e[i].z-=tmp;
			e[i^1].z+=tmp;
			d+=tmp;
			if(d==flow||dis[st]>=666)return d;
		}
	}
	if(dis[st]>=666)return d;
	cnt[dis[x]]--;
	if(cnt[dis[x]]==0)dis[st]=666;
	dis[x]++;
	cur[x]=elast[x];
	cnt[dis[x]]++;
	return d;
}
int L,R,mid,qans;
int id[N];
bool check(int mid)
{
	k=1;
	memset(elast,0,sizeof(elast));
	for(int i=1;i<=m;i++)add(st,i,1);
	for(int i=1;i<=m;i++)
	{
		id[i]=k+1;
		add(i,m+a[i].x,1);
		add(i,m+a[i].y,1);		
	}
	for(int i=1;i<=n;i++)add(m+i,en,mid);
	ans=0;
	bfs(en);
	while(dis[st]<666)ans+=dfs(st,1e9);
	if(ans>=m)return true;
	return false;
}
int main()
{
	scanf("%d%d",&n,&m);
	st=0,en=n+m+1;
	for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y);
	L=m/n,R=m;
	while(L<=R)
	{
		mid=(L+R)/2;
		if(check(mid))qans=mid,R=mid-1;
		else L=mid+1;
	}
	printf("%d\n",qans);
	check(qans);
	for(int i=1;i<=m;i++)
	{
		if(e[id[i]].z==0)printf("1\n");
		else printf("0\n");
	}
	return 0;
}