MatrixTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1893Accepted Submission(s): 1006
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
210 35 10310 3 32 5 36 7 1051 2 3 4 52 3 4 5 63 4 5 6 74 5 6 7 85 6 7 8 9
Sample Output
284680
Author
yifenfei
Source
Recommend
yifenfei|We have carefully selected several similar problems for you:33762448339534913313
题意：给出一个n*n的矩阵，每个点上都有一个值，现在从左上角沿着一条路径走到右下脚（只能向右或者向下），然后再从右下角回到左上角（只能向左或者向上），在这个过程中每个点只允许走一次，问路径上的权值之和最大为多少？
思路：这里用到费用流求解，首先添加一个超级源点s=0和超级汇点t=n*n+1，，然后对每个点拆点， i 向 i` 连边，容量为1，花费为该点的权值mp[i][j]，然后s与 1` 连边，容量为2，花费为0，n*n向t连边，容量为2，花费为0，最后矩阵中的点之间连边，容量为1，花费为0。最后答案为cost+mp[1][1]+mp[n][n]。注意数组的大小。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;const int MAXN = 2000; //注意数组的大小const int MAXM = 100000;struct Edge{int to,next,cap,flow,cost;}edge[MAXM];int head[MAXN],tol;int pre[MAXN],dis[MAXN];bool vis[MAXN];int N,n,m;void init(int n){N=n;tol=0;memset(head,-1,sizeof(head));}void addedge(int u,int v,int cap,int cost){edge[tol].to=v;edge[tol].cap=cap;edge[tol].cost=cost;edge[tol].flow=0;edge[tol].next=head[u];head[u]=tol++;edge[tol].to=u;edge[tol].cap=0;edge[tol].cost=-cost;edge[tol].flow=0;edge[tol].next=head[v];head[v]=tol++;}bool spfa(int s,int t){queue<int>q;for (int i=0;i<N;i++){dis[i]=-INF;vis[i]=false;pre[i]=-1;}dis[s]=0;vis[s]=true;q.push(s);while (!q.empty()){int u=q.front();q.pop();vis[u]=false;for (int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if (edge[i].cap > edge[i].flow && dis[v] < dis[u] + edge[i].cost){dis[v]=dis[u] + edge[i].cost;pre[v]=i;if (!vis[v]){vis[v]=true;q.push(v);}}}}if (pre[t]==-1) return false;else 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!=-1;i=pre[edge[i^1].to]){if (Min > edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;}for (int i=pre[t];i!=-1;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[MAXN][MAXN];int main(){#ifndef ONLINE_JUDGEfreopen("C:/Users/asus1/Desktop/IN.txt","r",stdin);#endifint i,j,t;while (~sf(n)){init(2*n*n+2);FRE(i,1,n)FRE(j,1,n)sf(mp[i][j]);addedge(0,1+n*n,2,0);addedge(n*n,2*n*n+1,2,0);FRE(i,1,n)FRE(j,1,n){addedge((i-1)*n+j,(i-1)*n+j+n*n,1,mp[i][j]);if (j+1<=n)addedge((i-1)*n+n*n+j,(i-1)*n+j+1,1,0);if (i+1<=n)addedge((i-1)*n+j+n*n,i*n+j,1,0);}int cost;int ans=minCostMaxflow(0,N-1,cost);printf("%d\n",cost+mp[1][1]+mp[n][n]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
在时光的激流中，我们总会长大。
