pku 3422 Kaka's Matrix Travels最大費用最大ストリーム

http://poj.org/problem?id=3422
/*
标题:n*nの矩形の四角い格子を与えて、(1,1)から右下にしか歩けないことを要求して、(i+1,j)あるいは(i+n,j)歩き終わるたびに格子の中の数を累積して、歩いた格子の中の数をゼロにして、kが得られる最大の数を聞く.
*/
/*
 ネットの流れのテーマの建図は肝心で、このテーマの建図はとても考えにくいです!まず取り外します.ここでは1つの点を2つの点に分割し、2つのエッジを確立し、1つは流量が1になり、重み値はmap[i][j]、もう1つは流量が無限で、重み値が0になった.注意この辺は、この店を通った後、map[i][j]が0になった後も、流量があり、重み値が0であることを保証するため、右下に流量が無限の重み値が0であることを確立するための辺である.最後に確立するのはスーパーソース点と汇点の辺で、すべて流量がkの重み値が0の辺で、k回歩くことを保証します.
*/
code:

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

#define maxn 5005

using namespace std;



const int inf = 99999999;



struct node

{

    int u,v;

    int c,w;

    int next;

}g[maxn*100];

int head[maxn],cnt,pre[maxn];

int dis[maxn],map[maxn][maxn];

bool inq[maxn];

int n,m,k,s,t,ans;



//       

void init()

{

    memset(head,-1,sizeof(head));

    cnt = 0;

}

//  ，          

void add(int u,int v,int c,int w)

{

    g[cnt].u = u; g[cnt].v = v; g[cnt].c = c; g[cnt].w = w;

    g[cnt].next = head[u]; head[u] = cnt++;



    g[cnt].u = v; g[cnt].v = u; g[cnt].c = 0; g[cnt].w = -w;

    g[cnt].next = head[v]; head[v] = cnt++;

}

void spfa()

{

    int i;

    queue<int>q;

    for (i = 0; i <= t; ++i)

    {

        dis[i] = -inf;

        inq[i] = false;

        pre[i] = -1;

    }

    q.push(s); inq[s] = true;

    dis[s] = 0;

    while (!q.empty())

    {

        int u = q.front(); q.pop();

        inq[u] = false;

        for (i = head[u]; i != -1; i = g[i].next)

        {

            int v = g[i].v;

            if (g[i].c && dis[v] < dis[u] + g[i].w)

            {

                dis[v] = dis[u] + g[i].w;

                pre[v] = i;//             

                if (!inq[v])

                {

                    inq[v] = true;

                    q.push(v);

                }

            }

        }

    }

}

void MCMF()

{

   while (1)

   {

       spfa();

       if (pre[t] == -1) break;

       int x = t,minf = inf;

       while (x != s)

       {

           minf = min(minf,g[pre[x]].c);

           x = g[pre[x]].u;

       }

       x = t;

       while (x != s)

       {

           g[pre[x]].c -= minf;

           g[pre[x]^1].c += minf;

           x = g[pre[x]].u;

       }

       ans += minf*dis[t];

   }

}

int main()

{

    int i,j;

    scanf("%d%d",&n,&k);

    int tmp = n*n;

    init();

    //        

    for (i = 1; i <= n; ++i)

    {

        for (j = 1; j <= n; ++j)

        {

            scanf("%d",&map[i][j]);

            int x = (i - 1)*n + j;

            int y = x + tmp;

            add(x,y,1,map[i][j]);

            add(x,y,inf,0);

            if (i < n) add(y,x + n,inf,0);

            if (j < n) add(y,x + 1,inf,0);

        }

    }

    s = 0; t = 2*tmp + 1;

    add(s,1,k,0);

    add(2*tmp,t,k,0);

    ans = 0;

    MCMF();

    printf("%d
",ans);

    return 0;

}