一道挺好的费用流模板。

当看到只能走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 
    
     using namespace std;const int NODE = 1000000;const int EDGE = 1000000;const int inf = 1e9;//Index of Edgestruct Edge{    int to, nxt, flow, cost;}edge[EDGE << 1];int head[NODE], cnt = 1;//Indexs of EK Network Flowint 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 Endint S, T;//The Indexs to record resultint maxflow, mincost;//Something for SPFAbool vis[NODE];queue
     
       que;//The functionsvoid 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 NODEsint start[60][60];int end[60][60];//main functionint 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;}//functionsbool 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];        }    }}