BZOJ 1001 [BeiJing2006]狼抓兔子

题目大意

给你一堆（无限个）兔子，从一个网格图的左上方的点跑到右下方的点。每个店有一个最大流量，如果你想截断这条路就需要花费流量同样的价格。求最小花费使得这一堆兔子到不了右下角。

这道题直接上最小割竟！然！可！以！A！ 之后就是板子

正解对偶图，之后会进行重构。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=1<<30;
int n,m,S,T,inx,ans,depth[2000010];
int to[6000010],nex[6000010],val[6000010],tot=1,head[2000010];
queue<int>q;
const int getid(int tx,int ty) {return (tx-1)*m+ty;}
void addedge(int tx,int ty,int tz)
{
	to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;
	to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot,val[tot]=tz;
}
bool bfs()
{
	while(!q.empty()) q.pop();
	q.push(S);
	memset(depth,-1,sizeof depth);
	depth[S]=0;
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		for(int i=head[tmp];i;i=nex[i])
			if(val[i]&&depth[to[i]]==-1)
			{
				depth[to[i]]=depth[tmp]+1;
				if(to[i]==T) return true;
				q.push(to[i]);
			}
	}
	return false;
}
int dinic(int pos,int left)
{
	if(pos==T) return left;
	int nleft=left;
	for(int i=head[pos];i;i=nex[i])
		if(val[i]&&depth[to[i]]==depth[pos]+1)
		{
			int tmp=dinic(to[i],min(nleft,val[i]));
			if(!tmp) depth[to[i]]=-1;
			nleft-=tmp;
			val[i]-=tmp;
			val[i^1]+=tmp;
			if(!nleft) break;
		}
	return left-nleft;
}
int main()
{
	scanf("%d%d",&n,&m);
	S=1,T=getid(n,m);
	for(int i=1;i<=n;++i)
		for(int j=2;j<=m;++j)
		{
			scanf("%d",&inx);
			int tmp=getid(i,j);
			addedge(tmp-1,tmp,inx);
		}
	for(int i=2;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			scanf("%d",&inx);
			addedge(getid(i,j),getid(i-1,j),inx);
		}
	for(int i=2;i<=n;++i)
		for(int j=2;j<=m;++j)
		{
			scanf("%d",&inx);
			addedge(getid(i,j),getid(i-1,j-1),inx);
		}
	while(bfs()) ans+=dinic(S,INF);
	printf("%d\n",ans);
	return 0;
}