HDU - 2686 Matrix

Matrix

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2869 Accepted Submission(s): 1550

Problem Description
Yifenfei very like play a number game in the n*n Matrix. A positive integer number is put in each area of the Matrix.
Every time yifenfei should to do is that choose a detour which frome the top left point to the bottom right point and than back to the top left point with the maximal values of sum integers that area of Matrix yifenfei choose. But from the top to the bottom can only choose right and down, from the bottom to the top can only choose left and up. And yifenfei can not pass the same area of the Matrix except the start and end.

Input
The input contains multiple test cases.
Each case first line given the integer n (2<n<30)
Than n lines,each line include n positive integers.(<100)

Output
For each test case output the maximal values yifenfei can get.

Sample Input
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

Sample Output
28
46
80

Author
yifenfei

Source
ZJFC 2009-3 Programming Contest

比较简单的一道费用流，挺像网络流24题当中的一道题。

考虑建图：

• 我们把每个点拆开，限流，费用为点的价值，流量为1
• 建立S连向第一个点，最后一个点连向T
• 最后补充第一个点入点与出点的一条边，流量为1，费用为0，因为起始点可以用两次，但价值使用一次。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+10,M=1e5+10;
int n,v[N],e[N],g[N][N],s,t,base,d[N];
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
inline int id(int x,int y){
	return (x-1)*n+y;
}
inline bool spfa(){
	int vis[N]={0};	vis[s]=1;	queue<int> q;	q.push(s);
	memset(d,inf,sizeof d);	d[s]=0;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u;	e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=inf;
}
inline int EK(){
	int res=0;
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=d[t]*mi;
	}
	return -res;
}
signed main(){
	while(~scanf("%d",&n)){
		tot=1;	memset(head,0,sizeof head);	s=0; t=n*n*2+1; base=n*n;
		for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	scanf("%d",&g[i][j]);
		add(s,1,2,0);	add(id(n,n)+base,t,2,0);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				add(id(i,j),id(i,j)+base,1,-g[i][j]);
				if(i<n)	add(id(i,j)+base,id(i+1,j),1,0);
				if(j<n) add(id(i,j)+base,id(i,j+1),1,0);
			}
		}
		add(1,1+base,1,0);	add(id(n,n),id(n,n)+base,1,0);
		printf("%d\n",EK());
	}
	return 0;
}