POJ 3422 最小费用最大流 zkw或者普通版本
建图的话
每个点拆成两个点u, u'，连一条容量为1费用为金币数的边，再连一条容量为k，费用为0的边
然后每个点和他右边或者下边的点连边 i'->j这样连
然后源点连1点，右下角那个点去连汇点，容量都为k，费用为0
普通写法
#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <queue>#include <deque>#include <map>#include <set>#define eps 1e-5#define MAXN 5555#define MAXM 55555#define INF 100000007using namespace std;struct EDGE{ int cost, cap, v; int next, re;}edge[MAXM];int head[MAXN], e;int vis[MAXN], d[MAXN];int ans, cost, src, des, n;void init(){ memset(head, -1, sizeof(head)); e = 0; ans = cost = 0;}void add(int u, int v, int cap, int cost){ edge[e].v = v; edge[e].cap = cap; edge[e].cost = cost; edge[e].re = e + 1; edge[e].next = head[u]; head[u] = e++; edge[e].v = u; edge[e].cap = 0; edge[e].cost = -cost; edge[e].re = e - 1; edge[e].next = head[v]; head[v] = e++;}int aug(int u, int f){ if(u == des) { ans += cost * f; return f; } vis[u] = 1; int tmp = f; for(int i = head[u]; i != -1; i = edge[i].next) if(edge[i].cap && !edge[i].cost && !vis[edge[i].v]) { int delta = aug(edge[i].v, tmp < edge[i].cap ? tmp : edge[i].cap); edge[i].cap -= delta; edge[edge[i].re].cap += delta; tmp -= delta; if(!tmp) return f; } return f - tmp;}bool modlabel(){ for(int i = 0; i <= n; i++) d[i] = INF; d[des] = 0; deque<int>Q; Q.push_back(des); while(!Q.empty()) { int u = Q.front(), tmp; Q.pop_front(); for(int i = head[u]; i != -1; i = edge[i].next) if(edge[edge[i].re].cap && (tmp = d[u] - edge[i].cost) < d[edge[i].v]) (d[edge[i].v] = tmp) <= d[Q.empty() ? src : Q.front()] ? Q.push_front(edge[i].v) : Q.push_back(edge[i].v); } for(int u = 1; u <= n; u++) for(int i = head[u]; i != -1; i = edge[i].next) edge[i].cost += d[edge[i].v] - d[u]; cost += d[src]; return d[src] < INF;}void costflow(){ while(modlabel()) { do { memset(vis, 0, sizeof(vis)); }while(aug(src, INF)); }}int nt, k;int main(){ int w; while(scanf("%d%d", &nt, &k) != EOF) { init(); for(int i = 1; i <= nt; i++) for(int j = 1; j <= nt; j++) { scanf("%d", &w); int id = (i - 1) * nt + j; add(id, id + nt * nt, 1, -w); add(id, id + nt * nt, k, 0); if(i < nt) add(id + nt * nt, id + nt, k, 0); if(j < nt) add(id + nt * nt, id + 1, k, 0); } src = nt * nt * 2 + 1; des = nt * nt * 2 + 2; n = des; add(src, 1, k, 0); add(nt * nt * 2, des, k, 0); costflow(); printf("%d\n", -ans); } return 0;}