题目：hdoj 3376 Matrix Again

题意：给出一个m*n的矩阵，然后从左上角到右下角走两次，每次仅仅能向右或者向下，出了末尾点其它仅仅能走一次，不能交叉，每次走到一个格子拿走这个格子中的数字，求价值最大？

分析：非常明显费用流。開始想的到一种建图方案，可是那样的话流量全为负值的话会成一个环，所以果断换了。

建图方案是：

首先拆点，每一个点拆成两个i 和 ii ，建边，费用为当前格子的值，流量为1，初始点和末尾点为2

然后每一个点向它的右边和下边分别建边，容量为1，费用为0

s 连接 左上角 流量 2 ，费用 0

右下角连接 t 。流量为 2 。费用为 0

PS：这个题目居然卡vector，的模拟自己实现邻接表，否则的话会超内存。

ac代码：

#include <cstdlib>

#include <cctype>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <string>

#include <iostream>

#include <sstream>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <fstream>

#include <numeric>

#include <iomanip>

#include <bitset>

#include <list>

#include <stdexcept>

#include <functional>

#include <utility>

#include <ctime>

using namespace std;

#define PB push_back

#define MP make_pair

#define Del(a,b) memset(a,b,sizeof(a))

typedef vector<int> VI;

typedef long long LL;

const LL inf = 0x3f3f3f3f;

const int N = 750000;

int cost,flow;

struct Node

{

    int from,to,cap,flow,cost;

    int next;

}e[N<<2];

int head[N],top;

void add_Node(int from,int to,int cap,int cost)

{

    e[top] = ((Node){from,to,cap,0,cost,head[from]});

    head[from] = top++;

    e[top] = ((Node){to,from,0,0,-cost,head[to]});

    head[to] = top++;

}

int vis[N],dis[N];

int father[N],pos[N];

bool BellManford(int s,int t,int& flow,int& cost)

{

    Del(dis,inf);

    Del(vis,0);

    queue<int> q;

    q.push(s);

    vis[s]=1;

    father[s]=-1;

    dis[s] = 0;

    pos[s] = inf;

    while(!q.empty())

    {

        int f = q.front();

        q.pop();

        vis[f] = 0;

        for(int i = head[f];i!=-1 ; i = e[i].next)

        {

            Node& tmp = e[i];

            if(tmp.cap>tmp.flow && dis[tmp.to] > dis[f] + tmp.cost)

            {

                dis[tmp.to] = dis[f] + tmp.cost;

                father[tmp.to] = i;

                pos[tmp.to] = min(pos[f],tmp.cap - tmp.flow);

                if(vis[tmp.to] == 0)

                {

                    vis[tmp.to]=1;

                    q.push(tmp.to);

                }

            }

        }

    }

    if(dis[t] == inf)

        return false;

    flow += pos[t];

    cost += dis[t]*pos[t];

    for(int u = t; u!=s ; u = e[father[u]].from)

    {

        e[father[u]].flow += pos[t];

        e[father[u]^1].flow -= pos[t];

    }

    return true;

}

int Mincost(int s,int t)

{

    flow = 0, cost = 0;

    while(BellManford(s,t,flow,cost));

    return cost;

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        Del(head,-1);top = 0;

        int num = n*n;

        int one,x;

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++){

                scanf("%d",&x);

                if(i==0 && j==0)

                    one = x;

                int tmp = 1;

                if(i==0 && j==0 || i==n-1 && j == n-1)

                    tmp = 2;

                add_Node(i*n+j,i*n+j+num,tmp,-x);

            }

        for(int i=0;i<n;i++)

        {

            for(int j=0;j<n;j++)

            {

                if((j+1)<n)

                    add_Node(i*n+j+num,i*n+j+1,1,0);

                if((i+1)<n)

                    add_Node(i*n+j+num,(i+1)*n+j,1,0);

            }

        }

        int s = 2*num+1 , t = s + 1;

        add_Node(s,0,2,0);

        add_Node(num+num-1,t,2,0);

        int ans = Mincost(s,t);

        printf("%d\n",-ans-x-one);

    }

    return 0;

}