【2025广东省队集训day10】这是第三题 做题记录

给定一个 $n\times m$ 的网格图，其中有一些格子上存在棋子（一个格子上最多只有一个棋子）。

你需要在空位处放最少的棋子，使得存在唯一的在棋子间两两配对的方案，满足每对棋子在同一行或者同一列。

输出最少添加多少个棋子，或者报告无解。

$1\le n,m\le 1000$。

首先建出一个左边有 $n$ 个点，右边有 $m$ 个点的二分图，边 $(i,j)$ 存在当且仅当 $(i,j)$ 这个点上有棋子。

那么匹配相当于匹配两条有公共点的边，考虑怎么判断匹配方案是否唯一。

注意到如果边形成了若干棵树，那么显然每棵树独立，而一棵树匹配方案可以这样确定：

• 随便定一个根，不断找到一个所有儿子都是叶子的点 $x$，如果 $x$ 有超过 $2$ 个儿子，那么匹配方案就不唯一（不合法）；否则若有 $2$ 个儿子就把这两条边拉出来匹配一下，有 $1$ 个儿子就和父亲那条边匹配（父亲的度数要减一）；
• 最后根的度数一定是 $0$ 或者 $2$，否则不合法；

而对于有环的情况，先不停执行上面的操作（剥叶子），不难发现由于最后剩下的是若干个边双所以肯定要么无解要么有多种匹配方案。

所以不妨先把刚开始不是森林的无解情况判掉。

那么现在有一些树不合法，我们能做的操作就是在这些不合法的树中某些点下面挂一些边是的所有树都合法，且最小化挂的边的数量。

为了表述方便，定义 $c$ 类点表示二分图的左部点（行），$r$ 类点表示二分图的右部点（列）。

考虑什么样的点能挂到不合法的树上，显然单点可以。而对于一棵大小 $\ge 2$ 的合法的树，不难发现随便定一个根后这个根可以被当作单点看待。而注意到我们还要求满足二分图的性质，所以单点只能提供对应类型的点，而大小 $\ge 2$ 的合法树两种类型的点都能提供。

对于某棵不合法的树 $t$，考虑设最终在这棵树的 $c$ 类点上挂了 $sc_t$ 条边，在 $r$ 类点上挂了 $sr_t$ 条边。

设 $Sc$ 为所有不合法的树的 $sc_t$ 的和，同理定义 $Sr$。再设 $ac$ 为 $c$ 类单点的数量，$ar$ 为 $r$ 类单点的数量，$ct$ 为大小 $\ge 2$ 的树的数量（无论是否合法）。

那么我们声称一组 $\{sc_t,sr_t\}$ 合法当且仅当：

$\max(Sc-ar,0)+\max(Sr-ac,0)\le ct-1$

显然这是必要的，否则最后会连出环（注意到一条边最多只能满足一棵非法树的挂载要求）。

充分性证明：

• 对于一棵非法树，先用单点满足它的要求，再用合法树；
• 如果所有非法树都不能通过上面的方法满足，那么由于每棵非法树都要挂至少一个点，总度数至少是非法树数，所以不满足不等式；

那么就简单了，设 $f_{u,k,v}$ 表示 $u$ 的子树，$sc_t$ 目前为 $k$，$u$ 的儿子个数为 $v$（剥叶子剥到 $u$ 时的儿子个数）的最小的 $sr_t$，转移类似树上背包。

时间复杂度 $O((n+m)^2)$，代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=1005,inf=1e8;

int n,m;
char a[S][S];
vector<int> g[S+S];
int fa[S+S];
int siz[S+S],f[S+S][S+S][3],tmp[S+S][3];
int res[S+S];

int fnd(int x){return fa[x]==x?x:fa[x]=fnd(fa[x]);}

int check(int u,int fa)
{
	int d=(fa!=0);
	for(int v:g[u])
	{
		if(v==fa) continue;
		int re=check(v,u);
		if(re==-1) return -1;
		d+=re;
		if(d>3) return -1;
	}
	if(fa==0&&d!=0&&d!=2) return -1;
	return d&1;
}

inline void tmin(int &x,int y){x=min(x,y);}

void dfs(int u,int fa)
{
	siz[u]=1;
	for(int i=0;i<=n+m;i++) for(int j=0;j<=2;j++) f[u][i][j]=inf;
	f[u][0][0]=0;
	if(u<=n) f[u][0][1]=1;
	else f[u][1][1]=0;
	for(int v:g[u])
	{
		if(v==fa) continue;
		dfs(v,u);
		for(int i=0;i<=siz[u]+siz[v];i++)
			for(int j=0;j<=2;j++) tmp[i][j]=inf;
		for(int i=0;i<=siz[u];i++)
			for(int j=0;j<=2;j++)
				for(int k=0;k<=siz[v];k++)
				{
					tmin(tmp[i+k][j],f[u][i][j]+f[v][k][1]);
					if(j<2) tmin(tmp[i+k][j+1],f[u][i][j]+min(f[v][k][0],f[v][k][2]));
				}
		siz[u]+=siz[v];
		for(int i=0;i<=siz[u];i++)
			for(int j=0;j<=2;j++)
				f[u][i][j]=tmp[i][j];
	}
}

int main()
{
	freopen("third.in","r",stdin);
	freopen("third.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>(a[i]+1);
	for(int i=1;i<=n+m;i++) fa[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]=='#')
			{
				// cout<<i<<' '<<n+j<<'\n';
				g[i].push_back(n+j);
				g[n+j].push_back(i);
				int rx=fnd(i),ry=fnd(n+j);
				if(rx==ry) return cout<<"-1\n",0;
				fa[rx]=ry;
			}
	int cn=0,cm=0,lim=0;
	for(int i=1;i<=n;i++) cn+=g[i].empty();
	for(int i=1;i<=m;i++) cm+=g[n+i].empty();
	vector<int> vec;
	for(int i=1;i<=n+m;i++)
	{
		if(g[i].empty()||fa[i]!=i) continue;
		lim++;
		if(check(i,0)==-1) vec.push_back(i);
	}
	lim--;
	// cout<<cn<<' '<<cm<<' '<<lim<<'\n';
	if(vec.empty()) return cout<<"0\n",0;
	for(int i=0;i<=n+m;i++) res[i]=inf;
	res[0]=0;
	int sm=0;
	for(int x:vec)
	{
		dfs(x,0);
		for(int j=0;j<=sm+siz[x];j++) tmp[j][0]=inf;
		for(int j=0;j<=sm;j++)
			for(int k=0;k<=siz[x];k++)
				tmin(tmp[j+k][0],res[j]+min(f[x][k][0],f[x][k][2]));
		sm+=siz[x];
		for(int j=0;j<=sm;j++) res[j]=tmp[j][0];
	}
	// cout<<res[1]<<'\n';
	int ans=inf;
	for(int sn=0;sn<=n+m;sn++)
	{
		int sm=res[sn];
		if(max(sn-cn,0)+max(sm-cm,0)<=lim) tmin(ans,sn+sm);
	}
	cout<<(ans==inf?-1:ans)<<'\n';
	return 0;
}