自动搬运

查看原文

来自洛谷，原作者为

	Drind 如果我此时的入机位置就是下一个，那我可以随机游走

搬运于2025-08-24 21:24:52，当前版本为作者最后更新于2023-05-31 21:41:45，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目给定一个 $01$ 矩阵每行和每列的 $1$ 的个数,求字典序最小的满足条件的矩阵.

如果只需要给出一个构造那么这题非常简单,只需要建立一个二分图,左边有 $n$ 个点，右边有 $m$ 个点，左部的第 $i$ 个点和源点连边,权值为 $r_i$ ,右部的第 $j$ 个点和汇点连边,权值为 $c_j$,每个左部点 $i$ 和右部点 $j$ 连边,权值为$1$.跑完最大流之后只需要把每条经过增广的边 $(i,j)$ 都输出 $1$,其他的输出 $0$ 就完成了构造.

显然这样的构造不满足字典序最小,于是我们想,对于每个边,肯定是更靠前的边更重要,那是否可以给每个边一个费用跑费用流呢?事实上也是不行的,如果要让边之间互相不影响的话,费用最大的边必须达到 $2^{nm}$,显然是会爆 long long 的,这种方法不可行.

那么,既然每条经过增广的边都代表这个点是 $1$ 的话,我们是否可以把这条边删掉再跑一遍最大流,判断这条边是否必须呢?

如果用这种思路做的话,首先我们先贪心地从大到小枚举每个点,先跑一遍最大流,然后看看这个点对应的边是否被增广,如果没有被增广说明这个点不必要,输出 $0$;如果这个点对应的边被增广,那么就删掉这条边,再跑一遍最大流,如果这次最大流还能找到一条增广路替代这条边的话,就说明这个点不必要,输出 $0$;如果第二次最大流找不到增广路了,说明这个点必要，输出 $1$.

不用考虑如果前面的点取 $0$ 后是否会对后面的点产生影响,因为只要求字典序最小,前面的尽可能小,后面的再大也无所谓.

代码:

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int to,nxt;
	int flow;
}edge[500001];//链式前向星

int cnt=1,s,t,n,m;
int head[1021];
int cur[1021];
int dep[1021];
int r[10001];
int c[10001];
int id[201][201];//id数组代表点对应的边，其中第一维的n+1代表连向汇点的边，第二位的m+1代表连向源点的边

void add(int u,int v,int w)
{
	edge[++cnt]={v,head[u],w};
	head[u]=cnt;
	edge[++cnt]={u,head[v],0};
	head[v]=cnt;
}//一次加正向和反向边
//以下为dinic板子
bool bfs()
{
	memset(dep,0,sizeof(dep));
	queue<int> q;
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];~i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if(!dep[v]&&edge[i].flow>0)
			{
				dep[v]=dep[u]+1;
				q.push(v);
				if(v==t)
					return true;
			}
		}
	} 
	return false;
}

int dfs(int u,int f)
{
	if(u==t)
		return f;
	int r=f;
	for(int i=head[u];~i&&r;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(dep[v]==dep[u]+1&&edge[i].flow>0)
		{
			int temp=dfs(v,min(r,edge[i].flow));
			if(!temp)
				dep[v]=0;
			edge[i].flow-=temp;
			edge[i^1].flow+=temp;
			r-=temp;
		}
	}
	return f-r;
}

int dinic()
{
	int mxflo=0;
	while(bfs())
	{
		mxflo+=dfs(s,1e9);
	}
	return mxflo;
}//以上为dinic板子

int check(int x,int y)//check函数代表第(x,y)个点是否必须
{
	dinic();
	if(!r[x]||!c[y]) return 0;//如果没有0可以放了，则输出1
	r[x]--,c[y]--;//假设放置0，行列0的数量都减一
	if(edge[id[x][y]].flow)//如果这个点未被增广，则不必要，输出0
	{
		edge[id[x][y]].flow=0;//删除这个点对应的边，以防今后再次使用
		return 1;
	}
	else
	{
		edge[id[x][y]^1].flow=0;//删除这条边，再次跑最大流，看看这条边是否必要
        edge[id[x][y]].flow=0;
		edge[id[x][m+1]^1].flow--;
		edge[id[x][m+1]].flow++;
		edge[id[n+1][y]^1].flow--;
		edge[id[n+1][y]].flow++;
		if(dinic()==1)//如果找到新的增广路替代则这个点不必要
			return 1;
		r[x]++;
		c[y]++;
		edge[id[n+1][y]].flow--;
		edge[id[n+1][y]^1].flow++;
		edge[id[x][m+1]].flow--;
		edge[id[x][m+1]^1].flow++;//这个点必要，恢复原状
		return 0;
	}
}

int main()
{
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	s=n+m+1;
	t=s+1;
	for(int i=1;i<=n;i++) cin>>r[i];
	for(int i=1;i<=m;i++) cin>>c[i]; 
	for(int i=1;i<=n;i++)
	{
		id[i][m+1]=cnt+1;
		add(s,i,r[i]);
		for(int j=1;j<=m;j++)
		{
			if(i==1)
			{
				id[n+1][j]=cnt+1;
				add(j+n,t,c[j]);
			}
			id[i][j]=cnt+1;
			add(i,j+n,1);
		}
	}//建图，初始化id数组
	for(int i=1;i<=n;i++) r[i]=m-r[i];//注意这里r和c数组已经被替换成0的数量
	for(int i=1;i<=m;i++) c[i]=n-c[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<1-check(i,j);//对于每个点判断
		cout<<endl;
	}
}