自动搬运

查看原文

来自洛谷，原作者为

	Rem_CandleFire 迷雾的丝是否会交织 我们的未来 终点

搬运于2025-08-24 22:41:32，当前版本为作者最后更新于2024-09-02 15:51:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析与做法

若将矩阵上的 $1$ 看做一个有向图，那么问题能转化成有向图上的最小可重链覆盖。

套路地，对于有向图做一个传递闭包（人话就是预处理出任意两点是否可达），这样我们就可以在上面做最小不可重链覆盖。

继续套路，将每个点拆成入点和出点，对于有向图上的一对可互相到达的点 $(u,v)$，连边 $u_{out}$ 和 $v_{in}$，那么二分图每一条边就对应着原图的某条边。

那么根据 Dilworth 定理 以及该文中的一些推理，答案就是有向图点数减去最大匹配。那么此题就做完了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,len;
int f[N][N],mch[N],vis[N];
struct node{ int x,y; } p[N];
vector<int> g[N];
void Add(int u,int v){ g[u].push_back(v),g[v].push_back(u); }
bool Match(int u)
{
	for(auto v:g[u])
	{
		if(vis[v]) continue;
		vis[v]=1;
		if(!mch[v]||Match(mch[v]))
			{ mch[v]=u; return true; }
	}
	return false;
}
int main()
{
	scanf("%d%d",&n,&m); char c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>c;
			if(c=='1') p[++len]={i,j};
		}
	for(int i=1;i<=len;i++)
		for(int j=i+1;j<=len;j++)
			if(p[i].x==p[j].x&&p[i].y+1==p[j].y||p[i].x+1==p[j].x&&p[i].y==p[j].y) f[i][j]=1;
	for(int k=1;k<=len;k++)
		for(int i=1;i<=len;i++)
			for(int j=1;j<=len;j++)
				f[i][j]|=(f[i][k]&f[k][j]);
	for(int i=1;i<=len;i++)
	{
		for(int j=i+1;j<=len;j++)
			if(f[i][j]) Add(i,j+len);
	}
	int sum=0;
	for(int i=1;i<=len;i++)
	{
		fill(vis,vis+1+len*2,0);
		if(Match(i)) sum++;
	}
	printf("%d",len-sum);

	return 0;
}