二分图-有障碍点建图

一种新的建图的思路的几个题

引入：USACO Muddy Fields

（贪心一发，如果重叠少的做法肯定优）

我们发现这个木板只有横竖两种摆放方式，而且如果都放在这里的话就重叠了

所以我们让每行每列为点，每个行列的交点为边建图

（而且这样建图直接具有二分图的性质）

然后是个最小点覆盖（每个边都要被涉及嘛（不懂的去看看边和点的定义））

建图：如果遇到障碍点标号就加一，障碍点在这里的定义是好地

具体就是这样的：

	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(g[i][j]==‘*‘) ++c1;
			while(g[i][j]==‘*‘) id1[i][j++]=c1;
		}
	}
	for(int j=1;j<=m;++j)
	{
		for(int i=1;i<=n;++i)
		{
			if(g[i][j]==‘*‘) ++c2;
			while(g[i][j]==‘*‘) id2[i++][j]=c2;
		}
	}

然后搬最大匹配

还有一个基本重题：ZOJ放置机器人

还是遇到障碍点就 \(+1\)，障碍点这一概念在本题应更好理解

\(Code\)：

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int N=2500;
	struct node{
		int to,nxt;
	}e[N<<5];
	int head[N],to[N],cnt,vis[N],n,m,c1,c2;
	inline void add(int x,int y)
	{
		e[++cnt].nxt=head[x]; e[cnt].to=y;
		return head[x]=cnt,void();
	}
	inline bool dfs(int x)
	{
		for(int i=head[x];i;i=e[i].nxt)
		{
			int t=e[i].to; if(vis[t]) continue;
			vis[t]=1; if(!to[t]||dfs(to[t])) return to[t]=x,1;
		} return 0;
	}
	inline int max_match()
	{
		int ans=0;
		for(int i=1;i<=c1;++i)
		{
			memset(vis,0,sizeof(vis)); 
			ans+=dfs(i);
		} return ans;
	}
	char g[N][N];
	int id1[N][N],id2[N][N];
	signed main()
	{
		n=read(); m=read(); 
		for(int i=1;i<=n;++i)
		{
			scanf("%s",g[i]+1);
		}
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=m;++j)
			{
				if(g[i][j]==‘*‘) ++c1;
				while(g[i][j]==‘*‘) id1[i][j++]=c1;
			}
		}
		for(int j=1;j<=m;++j)
		{
			for(int i=1;i<=n;++i)
			{
				if(g[i][j]==‘*‘) ++c2;
				while(g[i][j]==‘*‘) id2[i++][j]=c2;
			}
		}
		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(g[i][j]==‘*‘) add(id1[i][j],id2[i][j]);
		cout<<max_match()<<endl;
		return 0;
	}
}
signed main(){return yspm::main();}

二分图-有障碍点建图

原文：https://www.cnblogs.com/yspm/p/12650080.html