开了 O2 就 WA 一个,不开 O2 就 RE2 个。
可谓是大红大紫
萌新求救
#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;
}