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

叁歲伎倆 2022-08-13 07:28 197阅读 0赞

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

[hdoj 3376 Matrix Again]: http://acm.hdu.edu.cn/showproblem.php?pid=3376