hdoj 3376,2686 Matrix Again 【最小費用最大流】

題目：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;
}