程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Matrix (hdu 2686 最大費用最大流)

Matrix (hdu 2686 最大費用最大流)

編輯：C++入門知識

Matrix (hdu 2686 最大費用最大流)

Matrix

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1893 Accepted 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 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

Author yifenfei
Source ZJFC 2009-3 Programming Contest
Recommend yifenfei | We have carefully selected several similar problems for you: 3376 2448 3395 3491 3313
題意：給出一個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 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#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 pf          printf
#define DBG         pf(Hi
)
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)
{
    queueq;
    for (int i=0;i 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_JUDGE
    freopen(C:/Users/asus1/Desktop/IN.txt,r,stdin);
#endif
    int 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
,cost+mp[1][1]+mp[n][n]);
    }
    return 0;
}