Matrix

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

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

Sample Output

28
46
80

题意：从矩阵起点(1,1) -> (n,n) -> (1,1) 经过点的权值和最大是多少。每个点只能走一次，从(1,1) -> (n,n)只能往右或往下走，从(n,n) -> (1,1)只能往左或往上走。
分析：最小费用最大流。此题跟POJ_2135类似，只不过这里是点只能走一次，那么使用拆点法，把一个点(u)拆成两个点，连边 u -> u + n*n，容量为1，费用为0；然后对于每一个点u，连接右边点和下边点，容量为1，费用为权值的负值，这样子算出来后就是最小费用，再求负值就是最大权值和了。从起点跑一遍流量为2的最小费用流即可。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2686
代码清单：

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<cctype>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

#define end() return 0

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

const int maxn = 2000 + 5;
const int INF = 0x7f7f7f7f;

struct Edge{
    int from,to,cap,flow,cost;
    Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
};

struct MCMF{
    int n,m;
    vector<Edge>edge; //边数的两倍
    vector<int>G[maxn]; //邻接表，G[i][j]表示i的第j条边在e数组中的序号
    int inq[maxn]; //是否在队列
    int d[maxn]; //Bellman-Ford
    int p[maxn]; //上一条弧
    int a[maxn]; //可改进量

    void init(int n){
        this -> n = n;
        for(int i=0;i<=n;i++) G[i].clear();
        edge.clear();
    }

    void addEdge(int from,int to,int cap,int cost){
        edge.push_back(Edge(from,to,cap,0,cost));
        edge.push_back(Edge(to,from,0,0,-cost));
        m=edge.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    void show(){

    }

    bool BellmanFord(int s,int t,int& flow,int& cost){
        memset(d,INF,sizeof(d));
        memset(inq,0,sizeof(inq));
        d[s]=0; inq[s]=1; p[s]=0; a[s]=INF;

        queue<int>q;
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();
            inq[u]=0;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edge[G[u][i]];
                if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){
                        q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }

        if(d[t]==INF) return false;
        flow+=a[t];
        cost+=d[t]*a[t];
        if(flow==2) return false;
        for(int u=t;u!=s;u=edge[p[u]].from){
            edge[p[u]].flow+=a[t];
            edge[p[u]^1].flow-=a[t];
        }
        return true;
    }

    //需要保证初始网络中没有负权圈
    int MincostMaxflow(int s,int t){
        int flow=0,cost=0;
        while(BellmanFord(s,t,flow,cost));
        return cost;
    }
};


int N,tail;
int m[35][35];
MCMF mcmf;

void input(){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%d",&m[i][j]);
        }
    }
}

void createGraph(){
    mcmf.init(N*N*2);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i==N&&j==N) break;
            int u=(i-1)*N+j;
            int v1=(i-1)*N+j+1; //(i,j+1)
            int v2=i*N+j; //(i+1,j)
            if(i==1&&j==1){
                mcmf.addEdge(u,v1,1,-m[i][j+1]);
                mcmf.addEdge(u,v2,1,-m[i+1][j]);
            }
            else{
                mcmf.addEdge(u,u+N*N,1,0);
                if(j+1<=N)
                    mcmf.addEdge(u+N*N,v1,1,-m[i][j+1]);
                if(i+1<=N)
                    mcmf.addEdge(u+N*N,v2,1,-m[i+1][j]);
            }
        }
    }
}


void solve(){
    createGraph();
    printf("%d\n",m[1][1]-m[N][N]-mcmf.MincostMaxflow(1,N*N));
}

int main(){
    while(scanf("%d",&N)!=EOF){
        input();
        solve();
    }end();
}

秒客网

HDU_2686_Matrix(最小费用流)

Matrix

相关文章