0pts,且每个点的第一位都是4,求助
查看原帖
0pts,且每个点的第一位都是4,求助
254491
橙橙like海绵楼主2022/5/4 10:32
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=5e4+10;
const int inf=0x3f3f3f3f;
int n,m,s,t;
int fh[N],fl[N];
int dep[N],vis[N],cur[N];
char c[110][110];
int h[N],cnt=0;
struct node{
	ll cap,flow,nxt,to;
}e[N<<2];
void add(int u,int v,int w){
	e[cnt].cap=w;
	e[cnt].flow=0;
	e[cnt].nxt=h[u];
	e[cnt].to=v;
	h[u]=cnt++;
}
bool bfs(){
	for(int i=1;i<=2*n*m+2;i++) dep[i]=inf,vis[i]=0,cur[i]=h[i];
	queue<int> q;
	q.push(s);
	dep[s]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dep[v]>dep[u]+1&&e[i].cap>e[i].flow){
				dep[v]=dep[u]+1;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
					if(v==t) return true;
				}
			}
		}
	}
	return false;
}
ll dfs(int u,ll low){
	ll rlow=0;
	if(u==t) return low;
	for(int i=cur[u];i;i=e[i].nxt){
		cur[u]=i;
		int v=e[i].to;
		if(dep[v]==dep[u]+1&&e[i].cap>e[i].flow){
			if(rlow=dfs(v,min(low,e[i].cap-e[i].flow))){
				e[i].flow+=rlow;
				e[i^1].flow-=rlow;
				return rlow;
			}
		}
	}
	return 0;
}
ll dinic(){
	ll maxx=0,lo;
	while(bfs()){
		while(lo=dfs(s,inf)) maxx+=lo;
	}
	return maxx;
}
int code(int i,int j){
	return (i-1)*m+j;
}
void check(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<c[i][j];
		}
		puts("");
	}
	puts("");
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%d ",fh[code(i,j)]);
		}
		puts("");
	}
	puts("");
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%d ",fl[code(i,j)]);
		}
		puts("");
	}
	puts("");
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
		}
	}
	int cn1=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(c[i][j]=='#')
			{
				
				continue;
			} 
			else{
				if(c[i][j]=='*'){
					while(c[i][j]=='*'&&j<=m){
						fh[code(i,j)]=cn1;
						j++;
					}
					cn1++;
				}
				
			}
		}
	}
	int cn2=cn1;
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			if(c[i][j]=='#'){
				
				continue;
			}
			else{
				if(c[i][j]=='*'){
					while(c[i][j]=='*'&&i<=n){
						fl[code(i,j)]=cn2;
						i++;
					}
					cn2++;
				}
				
			}
		}
	}
	s=2*n*m+1;t=s+1;
	for(int i=1;i<cn1;i++){
		add(i,s,0);
		add(s,i,1);	
	}
	for(int i=1;i<cn2;i++){
		add(t,i+cn1-1,0);
		add(i+cn1-1,t,1);
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(c[i][j]=='*'){
				add(fl[code(i,j)],fh[code(i,j)],0);
				add(fh[code(i,j)],fl[code(i,j)],inf);
			}
		}
	}
	printf("%d",dinic());
	return 0;
}
2022/5/4 10:32
加载中...