! TJOIHEOI2016游戏

\(nm50\)

每个点连边，二分图匹配，时间复杂度\(O(n^4)\)

发现有奇环，只能带花树

SOL：

预处理出每行分为几块每块内只能放一个，列同理（以每个#分隔）

然后将*点的行块和列块连边，跑最大流即是答案

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int H=56,N=5e3,M=2e6,inf=1e9;
struct edge{
	int v,f,nxt;
}e[M];
int first[N],cur[N],cnt=1;
inline void add(int u,int v){
	e[++cnt]=(edge){v,1,first[u]};first[u]=cnt;
	e[++cnt]=(edge){u,0,first[v]};first[v]=cnt;
} 
int n,m,s,t,dis[N];
inline bool bfs(){
	static queue<int>q;
	while(!q.empty())q.pop();
	memset(dis,-1,sizeof(dis));
	dis[s]=1;
	q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=first[x],v;i;i=e[i].nxt){
			v=e[i].v;
			if(e[i].f&&dis[v]==-1){
				dis[v]=dis[x]+1;
				if(v==t)return 1;
				q.push(v); 
			}
		}
	}
	return 0;
}
int dfs(int x,int f){
	if(x==t||!f)return f;
	int used=0;
	for(int &i=cur[x],v,w;i;i=e[i].nxt){
		v=e[i].v;
		if(!e[i].f||dis[v]!=dis[x]+1)continue;
		w=dfs(v,min(f,e[i].f));
		if(!w)continue;
		e[i].f-=w;e[i^1].f+=w;
		f-=w;used+=w;
		if(!f)break;
	}
	return used;
}
inline int dinic(){
	int flow=0;
	while(bfs()){
		memcpy(cur,first,sizeof(first));
		flow+=dfs(s,inf);
	}
	return flow;
}
char ch[H][H];
int all,sh[H],sz[H];
vector<int>h[H],z[H];
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)scanf("%s",ch[i]+1);
	for(int i=1;i<=n;i++){
		ch[i][m+1]=‘#‘;
		for(int j=1;j<=m+1;j++)
			if(ch[i][j]==‘#‘)h[i].push_back(j);
		sh[i]=sh[i-1]+h[i].size();
	}
	for(int j=1;j<=m;j++){
		ch[n+1][j]=‘#‘;
		for(int i=1;i<=n+1;i++)
			if(ch[i][j]==‘#‘)z[j].push_back(i);
		sz[j]=sz[j-1]+z[j].size();
	}
	for(int i=1,x,y;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(ch[i][j]!=‘*‘)continue;
			x=lower_bound(h[i].begin(),h[i].end(),j)-h[i].begin()+1+sh[i-1];
			y=lower_bound(z[j].begin(),z[j].end(),i)-z[j].begin()+1+sz[j-1]+sh[n];
			add(x,y);
		}
	s=sh[n]+sz[m]+1;t=s+1;
	for(int i=1;i<=sh[n];i++)add(s,i);
	for(int i=1;i<=sz[m];i++)add(i+sh[n],t); 
	cout<<dinic();
	return (0-0);
}

! TJOIHEOI2016游戏

原文：https://www.cnblogs.com/aurora2004/p/12740093.html