程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 2686 Matrix(最大費用流)

HDU 2686 Matrix(最大費用流)

編輯:關於C++

Matrix

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



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
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 題意:給一個n*n的距陣,每個點都有一個值。問從(0,0)到(n-1, n-1)點(只能從左到右 或 從上到下)再回到(0,0)點(只能從右到左 或 下到上)經過的點的值總和最大是多少?每個點只能走一次。 解題:其實就是找兩條從(0,0)到(n-1,n-1)總和最大的路.拆點法。每個邊容量為1,費用:對於點的本身,邊權為點權,非點的邊權值為0。
#include
#include
#include
using namespace std;
const int MAXN = 10010;
const int MAXM = 1001000;
const int INF = 1<<30;
struct EDG{
    int to,next,cap,flow;
    int cost;  //單價
}edg[MAXM];
int head[MAXN],eid;
int pre[MAXN], cost[MAXN] ; //點0~(n-1)

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
void addEdg(int u,int v,int cap,int cst){
    edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst;
    edg[eid].cap=cap; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst;
    edg[eid].cap=0; edg[eid].flow=0; head[v]=eid++;
}

bool inq[MAXN];
bool spfa(int sNode,int eNode , int n){
    queueq;
    for(int i=0; i0 && cost[v]0){
        init();
        for(int i=0; i1) maxCost+=mapt[n-1][n-1];
        minCost_maxFlow(s , t , maxCost , n*n*2);
        printf("%d\n",maxCost);
    }
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved