LUOGU 题解 P2045 【方格取数加强版】

一道挺好的费用流模板。

当看到只能走K次时，根据直觉盲目猜测，初步判断可以转换为网络流的边流量限制，即限制汇入汇点的总流量。

然而这题还有一个“方格中的数字”，要求求最大，于是，就有了费用流的费用限制。

但是，费用流的全称为“最小费用最大流”，但是这题要求求最大“费用”（即数字之和），所以这题其实是“最大费用最大流”？？？

思考到这里，来想想怎么建图。

First

首先，方格中的数字，我们只能够取一次，于是我们可以考虑对每个点$x$进行拆点，拆分为“入点”与“出点”，分别记为$x‘$和$x‘‘$，然后连一条边，即$x‘\xrightarrow{flow=1,cost=a_{i,j}} x‘‘$，其中$a_{i,j}$表示每个点的数字，限制经过每个点获取的数字。

但是，每个点被取走数字后，并不是不能再走了，而只是数字变为$0$，于是我们再在$x’$与$x‘‘$之间建一条边$x‘\xrightarrow{flow=inf,cost=0}x‘‘$。

Second

然后呢，每个点可以走到下方的点或右方的点，于是我们将其连接：

设$x_{i,j}$、$x_{i,j+1}$与$x_{i+1,j}$

$x_{i,j}‘‘\xrightarrow{flow=inf,cost=0}x_{i,j+1}‘$。

$x_{i,j}‘‘\xrightarrow{flow=inf,cost=0}x_{i+1,j}‘$。

即表示可以走无数次，但不增加其$cost$。

Third

此时我们还没有连接源点与汇点，虽然连接哪里是显而易见的了……

我们设源点为$S$，汇点为$T$，因为我们只能走$K$次，所以我们把源点流出的流量与流入汇点的流量都设置为$K$，$cost$设为$0$，于是，建边部分就完成了！

About Network Flow

前面说了，这题的实质是“最大费用最大流”，所以直接照着板子打费用流是不行的。这里提供两种解决方法：

1、赋值费用时赋值为相反数，然后原来最大的就变成最小的……然后取$minflow$的相反数输出。

2、在SPFA部分的判断条件部分的$cost[y]>cost[x]+edge[i].cost$改为$cost[y]<cost[x]+edge[i].cost$，然后$mincost$就变成了$maxcost$辣。

先贴我的EK代码。

CODE：

//Luogu P2045
//Solution: EK Network Flow, Minimum Cost Maximum Flow 
//Written by MaxDYF
#include <bits/stdc++.h>
using namespace std;
const int NODE = 1000000;
const int EDGE = 1000000;
const int inf = 1e9;
//Index of Edge
struct Edge{
    int to, nxt, flow, cost;
}edge[EDGE << 1];
int head[NODE], cnt = 1;

//Indexs of EK Network Flow
int flow[NODE];
int cost[NODE];
int pre[NODE]; //record the last NODE of the present NODE in the road.
int last[NODE];//record the last EDGE of the present NODE.

//The Start and End
int S, T;

//The Indexs to record result
int maxflow, mincost;

//Something for SPFA
bool vis[NODE];
queue<int> que;

//The functions
void add(int, int, int, int);
bool spfa();
void work();

//All the things above here are about the Network Flow.
//And the things under here are about the Problem.
int a[60][60];//record the map

//They are for Spliting NODEs
int start[60][60];
int end[60][60];

//main function
int main()
{
    int n, k, cnt = 1;
    cin >> n >> k;
    //set the Start and the End
    S = 0;
    T = 2 * n * n + 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            cin >> a[i][j];
            a[i][j] = -a[i][j];
            //One of the MOST IMPORTANT things: split each NODE into 2 NODEs
            start[i][j] = ++cnt;
            end[i][j] = ++cnt;
        }
    }
    //Tips:
    //In this problem, the "cost" is refer to the Price of the Node.
    //So we have to get the "Max 'Cost'" instead of "Min 'Cost'".
    //To achieve our goal, we can turn the "cost"
    //to its opposite number.
    //And get the opposite number of the answer.
    //:) 
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            //Add edge for these two NODEs
            add(start[i][j], end[i][j], 1, a[i][j]);
            //set the Flow of the Edge between them to 1
            //to make sure that the Number can only be taken once.
            add(start[i][j], end[i][j], inf, 0);
            //to make sure that this Node can be walked many times.
            if(i < n)
                add(end[i][j], start[i+1][j], inf, 0);
            if(j < n)
                add(end[i][j], start[i][j+1], inf, 0);
            //just means they are connected, 
            //and can't get any "cost"(or price) any more.
        }
    }
    add(S, start[1][1], k, 0);
    add(end[n][n], T, k, 0);
    //make sure there are only "k" roads being collected.
    work();
    cout << -mincost;
}

//functions
bool spfa()
{
    //init
    memset(vis, 0, sizeof vis);
    memset(flow, 0x3f, sizeof flow);
    memset(cost, 0x3f, sizeof cost);
    cost[S] = 0;
    pre[T] = -1;
    que.push(S);
    vis[S] = 1;
    //main work of SPFA
    while (!que.empty())
    {
        int x = que.front();
        que.pop();
        vis[x] = 0;
        for (int i = head[x]; i; i = edge[i].nxt)
        {
            int y = edge[i].to;
            //if the present node is not the CHEAPEST
            if((cost[y] > cost[x] + edge[i].cost) && (edge[i].flow > 0))
            {
                //update the node
                //and its "pre" and "last"
                cost[y] = cost[x] + edge[i].cost;
                flow[y] = min(flow[x], edge[i].flow);
                pre[y] = x;
                last[y] = i;
                if(!vis[y])
                {
                    vis[y] = 1;
                    que.push(y);
                }
            }
        }
    }
    return pre[T] != -1; 
}
void add(int x, int y, int flow, int cost)
{
    edge[++cnt] = Edge{y, head[x], flow, cost};
    head[x] = cnt;
    edge[++cnt] = Edge{x, head[y], 0, -cost};
    head[y] = cnt;
}
void work()
{
    //EK Network Flow Algorithm
    //Nothing worth saying.
    //Isn't it?
    //If you can't understand it,
    //you'd better learn The EK Algorithm first.
    while(spfa())
    {
        maxflow += flow[T];
        mincost += flow[T] * cost[T];
        int now = T;
        while(now != S)
        {
            edge[last[now]].flow -= flow[T];
            edge[last[now] ^ 1].flow += flow[T];
            now = pre[now];
        }
    }
}

LUOGU 题解 P2045 【方格取数加强版】

原文：https://www.cnblogs.com/MaxDYF/p/10698949.html