题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2007

题目分类：网络流，最小割

题意：

给出一个网格图，一个角的海拔是1，对角的海拔是0，给出每条边上各个方向上的人流量，如果是下坡不消耗，是上坡消耗人流量和高度差的积的代价，让你给每个点安排海拔，求最优方案下总消耗。

题解：

考虑单独的一条路径，发现当海拔差集中在一段上一定是最优的，即【0,0，……，0,1,1，……，1,1】

问题转化为求网格图的最小割。

因为数据范围十分大，需要转换成对偶图用最短路来解。

程序：

#include<cstdio>
#include<queue>
using namespace std;
int dis[260000];
struct node
{
	int to,next,va;
}g[1200000];
int n,x1;
int ed,st[260000],inq[260000],S,T;
inline void add(int x,int y,int z)
{
	ed++;
	g[ed].to=y;
	g[ed].va=z;
	g[ed].next=st[x];
	st[x]=ed;
}
inline void spfa()
{
	queue<int>q;
	q.push(S);
	for (int i=S;i<=T;i++)
	{
		dis[i]=2100000000;
		inq[i]=0;
	}
	inq[S]=1;
	dis[S]=0;
	while (!q.empty())
	{
		x1=q.front();
		q.pop();
		inq[x1]=0;
		for (int i=st[x1];i!=0;i=g[i].next)
		{
			if(dis[g[i].to]>dis[x1]+g[i].va)
			{
				dis[g[i].to]=dis[x1]+g[i].va;
				if(inq[g[i].to]==0)
				{
					q.push(g[i].to);
					inq[g[i].to]=1;
				}
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	S=0;
	T=n*n+1;
	for (int i=0;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			scanf("%d",&x1);
			if(i==0)add(i*n+j,T,x1);
			else if(i==n)add(S,i*n-n+j,x1);
			else add(i*n+j,i*n-n+j,x1);
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<=n;j++)
		{
			scanf("%d",&x1);
			if(j==0)add(S,i*n-n+1,x1);
			else if(j==n)add(i*n-n+j,T,x1);
			else add(i*n-n+j,i*n-n+j+1,x1);
		}
	}
	for (int i=0;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			scanf("%d",&x1);
			if(i==0)add(T,i*n+j,x1);
			else if(i==n)add(i*n-n+j,S,x1);
			else add(i*n-n+j,i*n+j,x1);
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<=n;j++)
		{
			scanf("%d",&x1);
			if(j==0)add(i*n-n+1,S,x1);
			else if(j==n)add(T,i*n-n+j,x1);
			else add(i*n-n+j+1,i*n-n+j,x1);
		}
	}
	spfa();
	printf("%d\n",dis[T]);
	return 0;
}