自己造了几个数据是对的,提交爆零且输出全是0,求大佬帮忙调一下!!!
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=205;
int n,m;
char c[maxn][maxn],s,t;
int id(int x,int y)
{
return (x-1)*m+y;
}
int dep[maxn],gap[maxn];
int head[maxn*maxn*5],to[maxn*maxn*5],nxt[maxn*maxn*5],val[maxn*maxn*5],tot=1;
void add(int u,int v,int f)
{
to[++tot]=v;
nxt[tot]=head[u];
val[tot]=f;
head[u]=tot;
}
void bfs()
{
queue<int> q;
memset(gap,0,sizeof(gap));
memset(dep,-1,sizeof(dep));
q.push(t);
dep[t]=0;
gap[0]++;
while(!q.empty())
{
int tmp=q.front();
q.pop();
for(int i=head[tmp];i;i=nxt[i])
{
if(dep[to[i]]==-1)
{
q.push(to[i]);
dep[to[i]]=dep[tmp]+1;
gap[dep[to[i]]]++;
}
}
}
}
int maxflow;
int dfs(int now,int flow)
{
//cout <<now<<endl;
if(now==t)
{
// cout <<123;
maxflow+=flow;
return flow;
}
int use=0;
// cout <<head[now]<<endl;
for(int i=head[now];i;i=nxt[i])
{
//cout<<dep[to[i]]<<" "<<dep[now]<<endl;
if(val[i]&&dep[to[i]]+1==dep[now])
{
int f=dfs(to[i],min(flow-use,val[i]));
val[i]-=f,val[i^1]+=f,use+=f;
if(use==flow)
return flow;
}
}
if(--gap[dep[now]]==0)
dep[s]=t+1;
dep[now]++;
gap[dep[now]]++;
return use;
}
int isap()
{
maxflow=0;
bfs();
while(dep[s]<t+1)
dfs(s,0x3f3f3f3f3f);
return maxflow;
}
int heng[maxn][maxn],h,shu[maxn][maxn],cnt;
signed main()
{
cin >>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
while(c[i][j]!='*'&&c[i][j]!='x'&&c[i][j]!='#')
c[i][j]=getchar();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(c[i][j]=='#')
continue;
if(j==1||c[i][j-1]=='#')
cnt++;
heng[i][j]=cnt;
}
}
h=cnt;
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)
{
if(c[i][j]=='#')
continue;
if(i==1||c[i-1][j]=='#')
cnt++;
shu[i][j]=cnt;
}
}
s=0,t=cnt+1;
for(int i=1;i<=h;i++)
add(s,i,1),add(i,s,0);
for(int i=h+1;i<=cnt;i++)
add(i,t,1),add(t,i,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(c[i][j]=='*')
add(heng[i][j],shu[i][j],1),add(shu[i][j],heng[i][j],0);
}
cout <<isap()<<endl;
return 0;
}