蒟蒻求教
查看原帖
蒟蒻求教
193158
michael_song楼主2021/7/27 17:13

自己写的网络流,莫名其妙WA64,思路与题解对过了没有错

求帮忙谢谢

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=105,M=100005,inf=0x3f3f3f3f;
const int X[4]={0,-1,0,1},Y[4]={-1,0,1,0};
int mapl[N][N],head[N*N],prehead[N*N],result,total,cnt=1;
int m,n,s=10001,t=10002,lev[N*N];
inline int read()
{
	int w=1,f=0;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		f=f*10+c-'0';
		c=getchar();
	}
	return w*f;
}
inline int id(int x,int y)
{
	return n*(x-1)+y;
}
inline int minn(int x,int y)
{
	if(x<y)
		return x;
	else
		return y;
}
struct edge
{
	int u,v,w,next;
}e[M];
void addedge(int u,int v,int w)
{
	e[++cnt].next=head[u];
	head[u]=cnt;
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
}
void edgecreation(int x,int y)
{
	int prex,prey;
	for(int i=0;i<4;i++)
	{
		prex=x+X[i],prey=y+Y[i];
		if(prex<=m&&prex>=1&&prey<=n&&prey>=1)
		{
			addedge(id(prex,prey),id(x,y),inf);
			addedge(id(x,y),id(prex,prey),0);
		}
	}
}
bool bfs()
{
	memset(lev,inf,sizeof(lev));
	queue<int> Q;
	Q.push(s);
	lev[s]=1;
	prehead[s]=head[s];
	while(!Q.empty())
	{
		int u=Q.front();
		Q.pop();
		for(int i=head[u];i;i=e[i].next)
		{	
			if(e[i].w>0&&lev[e[i].v]==inf)
			{
				int v=e[i].v;
				lev[v]=lev[u]+1;
				prehead[v]=head[v];
				Q.push(v);
				if(v==t)
					return true;
			}
		}
	}
	return false;
}
int searchl(int u,int val)
{
	int k,ans=0;
	if(u==t)
		return val;
	for(int i=prehead[u];i!=0&&val!=0;i=e[i].next)
	{
		prehead[u]=i;
		if(lev[e[i].v]==lev[u]+1&&e[i].w>0)
		{
			int v=e[i].v;
			k=searchl(v,minn(e[i].w,val));
			if(!k)
				lev[v]=inf;
			ans+=k;
			val-=k;
			e[i].w-=k;
			e[i^1].w+=k;
		}
	}
	return ans;
}
int main()
{
	m=read();n=read();
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			mapl[i][j]=read();
			total+=mapl[i][j];
		}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			if(!(id(i,j)%2))
			{
				addedge(s,id(i,j),mapl[i][j]);
				addedge(id(i,j),s,0);
			}
			else
			{
				addedge(id(i,j),t,mapl[i][j]);
				addedge(t,id(i,j),0);
			}
		}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			if((id(i,j)%2))
				edgecreation(i,j);
	while(bfs())
		result+=searchl(s,inf);
	printf("%d",total-result);
	return 0;
}
2021/7/27 17:13
加载中...