AcWing 382. K取方格数（费用流）

本文主要是介绍AcWing 382. K取方格数（费用流），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在一个N*N的矩形网格中，每个格子里都写着一个非负整数。

可以从左上角到右下角安排K条路线，每一步只能往下或往右，沿途经过的格子中的整数会被取走。

若多条路线重复经过一个格子，只取一次。

求能取得的整数的和最大是多少。

输入格式
第一行包含两个整数N和K。

接下来N行，每行包含N个不超过1000的整数，用来描述整个矩形网格。

输出格式
输出一个整数，表示能取得的最大和。

数据范围
1≤N≤50,
0≤K≤10
输入样例：
3 2
1 2 3
0 2 1
1 4 2
输出样例：
15

思路：
费用流就是，每个边在有容量限制 $c (x, y)$ 的基础上，再增加了单位费用 $w (x, y)$ 。
当这个边的流量为 $f (x, y)$ 时，对应费用为 $f (x, y) * w (x, y)$ 。
在最大流的基础上求最小（最大）费用，称为费用流。

本题要求从 $(1, 1)$ 经过 $k$ 条路径到 $(n, n)$ ，可以作为容量为 $k$ 的最大流。
且每个格子只取一次，而费用则与格子的数有关。

本题就可以将每个格子拆成入点和出点。
入点向出点连两条边，一条容量为1，费用为格子值；
另一条边容量为k-1，费用为0。

然后每个格子的出点向相邻右边和下边的格子的入点连一条容量为 $k$ ，费用为 $0$ 的边。

跑出费用流就是结果了。

spfa费用流

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 5010, M = 200010;
int ver[M], edge[M], cost[M], Next[M], head[N];
int d[N], incf[N], pre[N], v[N];
int n, k, tot, s, t, maxflow, ans;void add(int x, int y, int z, int c) {// 正向边，初始容量z，单位费用cver[++tot] = y, edge[tot] = z, cost[tot] = c;Next[tot] = head[x], head[x] = tot;// 反向边，初始容量0，单位费用-c，与正向边“成对存储”ver[++tot] = x, edge[tot] = 0, cost[tot] = -c;Next[tot] = head[y], head[y] = tot;
}bool spfa() {queue<int> q;memset(d, 0xcf, sizeof(d)); // -INFmemset(v, 0, sizeof(v));q.push(s); d[s] = 0; v[s] = 1; // SPFA 求最长路incf[s] = 1 << 30; // 增广路上各边的最小剩余容量while (q.size()) {int x = q.front(); v[x] = 0; q.pop();for (int i = head[x]; i; i = Next[i]) {if (!edge[i]) continue; // 剩余容量为0，不在残量网络中，不遍历int y = ver[i];if (d[y]<d[x] + cost[i]) {d[y] = d[x] + cost[i];incf[y] = min(incf[x], edge[i]);pre[y] = i; // 记录前驱，便于找到最长路的实际方案if (!v[y]) v[y] = 1, q.push(y);}}}if (d[t] == 0xcfcfcfcf) return false; // 汇点不可达，已求出最大流return true;
}// 更新最长增广路及其反向边的剩余容量
void update() {int x = t;while (x != s) {int i = pre[x];edge[i] -= incf[t];edge[i ^ 1] += incf[t]; // 利用“成对存储”的xor 1技巧x = ver[i ^ 1];}maxflow += incf[t];ans += d[t] * incf[t];
}int num(int i,int j,int k) {return (i - 1) * n + j + k * n * n;
}int main() {scanf("%d%d",&n,&k);s = 1,t = 2 * n * n;tot = 1;for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {int c;scanf("%d",&c);add(num(i,j,0),num(i,j,1),1,c); //表示取这个数，流量为1，只能取一次add(num(i,j,0),num(i,j,1),k-1,0); //不取这个数，流量为k-1if(j < n) add(num(i,j,1),num(i,j + 1,0),k,0);if(i < n) add(num(i,j,1),num(i + 1,j,0),k,0);}}while(spfa()) update();printf("%d\n",ans);return 0;
}

dij费用流
引入“势函数”，也就是每个边加权，避免负边

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
#include <math.h>
using namespace std;#define INF 0x3f3f3f3fint n , k, tot = 0;
const int N = 55;
struct e
{int t;int c;int w;int next;
}edge[N*N*N];
int head[N*N*N] , h[N*N*N], dis[N*N*N], pre[N*N*N], pc[N*N*N], st, ed;
int ansflow , anscost, cnt;
void add(int f, int t, int c, int w)
{edge[cnt].t = t;edge[cnt].c = c;edge[cnt].next = head[f];edge[cnt].w = w;head[f] = cnt ++;edge[cnt].t = f;edge[cnt].c = 0;edge[cnt].next = head[t];edge[cnt].w = -w;head[t] = cnt ++;
}
struct node{int v, val;node(int a, int b):v(a), val(b){}bool operator < (const node& no) const{// return val > no.val; //最小费用return val < no.val; //最大费用}
};
void dij()
{priority_queue < node > q;while(true) //从汇点出发，不断寻找花费最短路作为增广路{for ( int i = 0 ; i <= ed ; i ++)dis[i] = -999999999;dis[st] = 0;pre[st] = -1;pc[st] = INF; //用于记录该增广路所能承受的最大流q.push(node(st,0));while(!q.empty()) //采用堆优化的dij寻找{node p = q.top();q.pop();int u = p.v;if(p.val < dis[u]) continue;for(int i = head[u] ; i != -1 ; i = edge[i].next){int v = edge[i].t , c = edge[i].c, w = edge[i].w;int ww = w + h[u] - h[v]; //引入势函数作为新权，保证正数，从而让成功，类似于Johnson算法if(c > 0 && dis[u] + ww > dis[v]){dis[v] = dis[u] + ww; //修改距离q.push(node(v,dis[v]));pre[v] = i; //记录路径pc[v] = min(pc[u],c); //修改最大流}}}if(dis[ed] == -999999999) //如果为INF说明不存在增广路，跳出即可break;for(int i = 1 ; i <= ed ; i ++) h[i] += dis[i]; //更新势函数int nowflow = pc[ed];ansflow += nowflow;anscost += h[ed]*nowflow;for(int i = ed ; pre[i] != -1 ; i = edge[pre[i]^1].t) //递归回溯路径，改变流大小{edge[pre[i]].c -= nowflow;edge[pre[i]^1].c += nowflow;}}
}int num(int i,int j,int k) {return (i - 1) * n + j + k * n * n;
}int main() {memset(head,-1,sizeof(head));scanf("%d%d",&n,&k);st = 1,ed = 2 * n * n;for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {int c;scanf("%d",&c);add(num(i,j,0),num(i,j,1),1,c); //表示取这个数，流量为1，只能取一次add(num(i,j,0),num(i,j,1),k-1,0); //不取这个数，流量为k-1if(j < n) add(num(i,j,1),num(i,j + 1,0),k,0);if(i < n) add(num(i,j,1),num(i + 1,j,0),k,0);}}dij();printf("%d\n",anscost);return 0;
}