自己写的网络流,莫名其妙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;
}