P4001 [ICPC-Beijing 2006]狼抓兔子

题目地址

易错点：

• 必须熟练掌握当无法在该点继续流量时直接剪枝（d[x]=0）的操作.
• 无向图的最大流由于两边都可增广，应当全部设置为相同的容量.
• 特殊矩阵图的构造.

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=1000010,MAXM=1000010;
struct Edge{int from,to,w,nxt;
}e[MAXM*6];
int head[MAXN*6],edgeCnt=1;
void addEdge(int u,int v,int w){e[++edgeCnt].from=u;e[edgeCnt].to=v;e[edgeCnt].w=w;e[edgeCnt].nxt=head[u];head[u]=edgeCnt;
}
int s,t;
int d[MAXN*6];
bool bfs(){memset(d,0,sizeof(d));queue<int> q;d[s]=1;q.push(s);while(!q.empty()){int nowV=q.front();q.pop();for(int i=head[nowV];i;i=e[i].nxt){int nowNode=e[i].to;if(e[i].w&&(!d[nowNode])){d[nowNode]=d[nowV]+1;if(nowNode==t)return 1;q.push(nowNode);}}}return 0;
}
int Dinic(int x,int flow){if(x==t)return flow;int rest=flow;for(int i=head[x];i&&rest;i=e[i].nxt){int nowV=e[i].to;if(d[nowV]==d[x]+1&&e[i].w){int k=Dinic(nowV,min(rest,e[i].w));if(!k)d[nowV]=0;e[i].w-=k,e[i^1].w+=k;rest-=k;}}return flow-rest;
}
int m;
int getHash(int i,int j){return (i-1)*m+j;
}
const int INF=2e9;
int main(){int n;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m-1;j++){int u,v,w;scanf("%d",&w);u=getHash(i,j),v=getHash(i,j+1);addEdge(u,v,w);addEdge(v,u,w);}}for(int i=1;i<=n-1;i++){for(int j=1;j<=m;j++){int u,v,w;scanf("%d",&w);u=getHash(i,j),v=getHash(i+1,j);addEdge(u,v,w);addEdge(v,u,w);}}for(int i=1;i<=n-1;i++){for(int j=1;j<=m-1;j++){int u,v,w;scanf("%d",&w);u=getHash(i,j),v=getHash(i+1,j+1);addEdge(u,v,w);addEdge(v,u,w);}}s=1,t=getHash(n,m);int ans=0;while(bfs()){ans+=Dinic(s,INF);}printf("%d\n",ans);return 0;
}