HDU 2686 Matrix(最大費用流)
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);
}
}
