和HDOJ 2686 一样，只是范围不同

最大费用最大流。。。。。

与最小费用最大流的区别用／／／／／／／／／／／／标出来了

对于detour，在源点和汇点处的边的流量为2

对于每个点只能经过一次，拆点，两个点直接建一条流量为1，费用为mp【i】【j】的边

对于每个点可以走到他的左边和下边：连一个费用为0流量大于1的边

Matrix Again

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 2880    Accepted Submission(s): 846

2
10 3
5 10
3
10 3 3
2 5 3
6 7 10
5
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9

28
46
80

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int maxn=800000;
const int INF=0x3f3f3f3f;
const int inf=9999;

struct Edge
{
	int to,next,cap,flow,cost;
}edge[4000000];

int Adj[maxn],Size,N,n;

void init()
{
	Size=0; memset(Adj,-1,sizeof(Adj));
}

void addedge(int u,int v,int cap,int cost)
{
	edge[Size].to=v;
	edge[Size].next=Adj[u];
	edge[Size].cost=cost;
	edge[Size].cap=cap;
	edge[Size].flow=0;
	Adj[u]=Size++;
}

void Add_Edge(int u,int v,int cap,int cost)
{
	//cout<<u<<" "<<v<<" "<<cap<<" "<<cost<<endl;
	addedge(u,v,cap,cost);
	addedge(v,u,0,-cost);
}

int dist[maxn],vis[maxn],pre[maxn];

bool spfa(int s,int t)
{
	queue<int> q;
	for(int i=0;i<n;i++)
	{
		dist[i]=-INF;vis[i]=false; pre[i]=-1;//////////////////////
	}
	dist[s]=0; vis[s]=true; q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=Adj[u];~i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(edge[i].cap>edge[i].flow&&
				dist[v]<dist[u]+edge[i].cost)/////////////////////
			{
				dist[v]=dist[u]+edge[i].cost;
				pre[v]=i;
				if(!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
	if(pre[t]==-1) return false;
	return true;
}

int MinCostMaxFlow(int s,int t,int& cost)
{
	int flow=0;
	cost=0;
	while(spfa(s,t))
	{
		int Min=INF;
		for(int i=pre[t];~i;i=pre[edge[i^1].to])
		{
			if(Min>edge[i].cap-edge[i].flow)
				Min=edge[i].cap-edge[i].flow;
		}
		if(Min==0) break;
		for(int i=pre[t];~i;i=pre[edge[i^1].to])
		{
			edge[i].flow+=Min;
			edge[i^1].flow-=Min;
			cost+=edge[i].cost*Min;
		}
		flow+=Min;
	}
	return flow;
}

int mp[1000][1000];

int main()
{
	while(scanf("%d",&N)!=EOF)
	{
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				scanf("%d",&mp[i][j]);
		init();
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				int a=i*N+j;
				int b=a+N*N;
				Add_Edge(a,b,1,mp[i][j]);
				if((i==0&&j==0)||(i==N-1&&j==N-1))
				{
					Add_Edge(a,b,1,mp[i][j]);/////////////
				}
				if(j!=N-1)
				{
					Add_Edge(b,a+1,inf,0);
				}
				if(i!=N-1)
				{
					Add_Edge(b,a+N,inf,0);
				}
			}
		}
		int S=0,T=N*N*2-1;
		n=T+1;

		int FLOW,COST;
		FLOW=MinCostMaxFlow(S,T,COST);
		//cout<<"FLOW: "<<FLOW<<" COST: "<<COST<<endl;
		printf("%d\n",COST-mp[0][0]-mp[N-1][N-1]);///////////////////
	}
	return 0;
}