有点纳闷
查看原帖
有点纳闷
227824
JK_LOVER楼主2020/8/8 20:00

开了 O2O2WAWA 一个,不开 O2O2RE2RE2 个。 可谓是大红大紫 萌新求救

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int read(){int x;scanf("%d",&x);return x;}
struct Edge{int to,nxt,flow,cap;}e[N<<1];
int cnt = 1,R,C,S,T,cur[N],head[N],dis[N];
queue<int> Q;
void add(int x,int y,int cap){
	e[++cnt].nxt = head[x];e[cnt].to = y;e[cnt].flow = 0;e[cnt].cap = cap;head[x] = cnt;
	e[++cnt].nxt = head[y];e[cnt].to = x;e[cnt].flow = 0;e[cnt].cap = 0;head[y] = cnt;
}
bool bfs(int s,int t){
	while(!Q.empty()) Q.pop();
	memset(dis,0,sizeof(dis));dis[s] = 1;Q.push(s);
	while(Q.size()){
		int x = Q.front();Q.pop();
		for(int i = head[x];i;i = e[i].nxt){
			if(!dis[e[i].to] && e[i].cap > e[i].flow){
				Q.push(e[i].to);dis[e[i].to] = dis[x] + 1;
				if(e[i].to == t) return true;
			}
		}
	}
	return false;
}
int dfs(int x,int a,int t){
	if(x == t|| a == 0) return a;
	int flow = 0,f;
	for(int i = cur[x];i;i = e[i].nxt){
		int y = e[i].to;
		if(dis[y] == dis[x] + 1 && (f=dfs(y,min(a,e[i].cap-e[i].flow),t))>0)		
		{
			e[i].flow += f;e[i^1].flow -= f;flow += f;a -= f;cur[x] = i;
			if(!a) break; 
		}
	}
	return flow;
}
char ch[N][N];
int col[N][N][2],Colx,Coly,vis[N][N];
int main()
{
	R = read();C = read();
	for(int i = 1;i <= R;i++){
		for(int j = 1;j <= C;j++){
			cin>>ch[i][j];
			if(ch[i][j]=='*' && ch[i-1][j] == '*') 
			col[i][j][1] = col[i-1][j][1];
			else if(ch[i][j]=='*')col[i][j][1] = ++Colx;
			if(ch[i][j]=='*' && ch[i][j-1] == '*') 
			col[i][j][0] = col[i][j-1][0];
			else if(ch[i][j]=='*')col[i][j][0] = ++Coly;
		}
	}
	S = 0;T = Colx+Coly+1;
	for(int i = 1;i <= Colx;i++) add(S,i,1);
	for(int i = 1;i <= Coly;i++) add(i+Colx,T,1);
	for(int i = 1;i <= R;i++){
		for(int j = 1;j <= C;j++){	
			if(ch[i][j]=='.') continue;
			int y = col[i][j][0],x = col[i][j][1];
			if(!vis[x][y]) add(x,y+Colx,1),vis[x][y] = 1;
		}
	}
	int maxflow = 0;
	while(bfs(S,T)){
		for(int i = 0;i < T;i++) cur[i] = head[i];
		maxflow += dfs(S,0x3f3f3f3f,T);
	}
	printf("%d\n",maxflow);
	return 0;
}
2020/8/8 20:00
加载中...