零分求助!!!
查看原帖
零分求助!!!
369181
bamboo12345楼主2022/3/11 11:05

自己造了几个数据是对的,提交爆零且输出全是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;
}
2022/3/11 11:05
加载中...