POJ 3422 Kaka's Matrix Travels(最大費用ストリーム+取外し点)

テーマリンク:http://poj.org/problem?id=3422
Description
On an N × N checkboard with a non-negative number in each grid、ka starts his matravels with SUM = 0.For each travel、Kaka moves one rook from the left-up grid to the right-bottom one、tang care that the rook moves to the right or down.Kaka adds the number to SUM in each grid the rook visited，and replacces it with zero.It is not difficult to know the maximm SUM ka can obtain for his first travel.Now Kaka is wondering what is the maximm SUM ヘcan obtain after his Kth travel.Note the SUM is accumultive during the K trvels.
Input
The first line contains two integers N and K （1≦ N ≤50,0≦ K ≦10）described above.The follwing N LINE represents the matirix.You can assiume the numbers in the matrix are no more than 1000.
Output
The maximum SUM Kaka can obtain after his Kth travel.
Sample Input

3 2
1 2 3
0 2 1
1 4 2

Sample Output

15

ソurce
POJ Monthly-2007.16,Huagng，Jinsong
件名:
行列の中で、すべての格子の中に負数ではないのがあります。将棋の車を左上から右下まで歩いて、k回歩いて、毎回1歩しか歩けません。毎回右か下に行くしかないです。通過した数字は価値（費用）です。そして、ある点を通った後、再度この点を歩くと、その費用はゼロです。最大と最大を求めます。
PS:
最大費用の流れの問題は、
1、解体して辺を建てる：各点を二つの点に分解してからこの二つの点の間に二つの辺を作る：
第一条：彼らの間の費用は取り外されたポイントの正数の反対数である（これで最小費用の最大フローで解決できます。最終的な答えは反対の数に行くと最大費用になります。）流量は1となります。
第二条：費用は0で、流量はk-1とする。
2、それぞれ右に行って、下に建設する費用は0で、流量はkの辺です。
//最大費用最小ストリームは追加側で位置を変えてくれればいいです。/最大費用の最大ストリームを求めるなら、費用を逆の数に変えて、最小費用で最大のフローで解決すればいいです。
コードは以下の通りです

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 10000;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int to, next, cap, flow, cost;
    int x, y;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N, M;
int map[MAXN][MAXN];
void init()
{
    N = MAXN;
    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;
}
//       ， cost       
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 main()
{
    int n, k;
    while(~scanf("%d%d",&n,&k))
    {
        init();//  
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                int tt = (i-1)*n+j;
                addedge(tt*2,tt*2+1,1,-map[i][j]);//  ，           ，   1
                addedge(tt*2,tt*2+1,k-1,0);//       0，   k-1  
                //printf("tt:%d tt*2:%d tt*2+1:%d ",tt,tt*2,tt*2+1);
            }
            //printf("
");
        }
        for(int i = 1; i <= n; i++)//  
        {
            for(int j = 1; j < n; j++)
            {
                int tt = (i-1)*n+j;//   2  
                addedge(tt*2+1,(tt+1)*2,k,0);
                //printf("tt:%d tt*2:%d (tt+1)*2:%d
",tt,tt*2,(tt+1)*2);
            }
        }
        for(int i = 1; i < n; i++)//  
        {
            for(int j = 1; j <= n; j++)
            {
                int tt = (i-1)*n+j;
                addedge(tt*2+1,(tt+n)*2,k,0);
                //printf("tt:%d tt*2:%d (tt+n)*2:%d
",tt,tt*2,(tt+n)*2);
            }
        }
        int beg = 1;//    
        int end = 2*n*n+2;//    
        addedge(beg,2,k,0);//    ,   1，   0
        addedge(2*n*n+1,end,k,0);//       1，   0
        int ans = 0;
        minCostMaxflow(beg,end,ans);
        //minCostMaxflow(2,2*n*n+1,ans);
        printf("%d
",-ans);//          
    }
    return 0;
}