POJ 3422 最小费用最大流 zkw或者普通版本
建图的话
每个点拆成两个点u, u'，连一条容量为1费用为金币数的边，再连一条容量为k，费用为0的边
然后每个点和他右边或者下边的点连边 i'->j这样连
然后源点连1点，右下角那个点去连汇点，容量都为k，费用为0
普通写法
[cpp]
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 5555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{
int v, cap, cost, next, re; // re记录逆边的下标。
} edge[MAXM];
int n, m, ans, flow, src, des;
int e, head[MAXN];
int que[MAXN], pre[MAXN], dis[MAXN];
bool vis[MAXN];
void init()
{
e = ans = flow = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int cap, int cost)
{
edge[e].v = v;
edge[e].cap = cap;
edge[e].cost = cost;
edge[e].next = head[u];
edge[e].re = e + 1;
head[u] = e++;
edge[e].v = u;
edge[e].cap = 0;
edge[e].cost = -cost;
edge[e].next = head[v];
edge[e].re = e - 1;
head[v] = e++;
}
bool spfa()
{
int i, h = 0, t = 1;
for(i = 0; i <= n; i ++)
{
dis[i] = INF;
vis[i] = false;
}
dis[src] = 0;
que[0] = src;
vis[src] = true;
while(t != h)
{
int u = que[h++];
h %= n;
vis[u] = false;
for(i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(edge[i].cap && dis[v] > dis[u] + edge[i].cost)
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
que[t++] = v;
t %= n;
}
}
}
}
if(dis[des] == INF) return false;
return true;
}
void end()
{
int u, p, mi = INF;
for(u = des; u != src; u = edge[edge[p].re].v)
{
p = pre[u];
mi = min(mi, edge[p].cap);
}
for(u = des; u != src; u = edge[edge[p].re].v)
{
p = pre[u];
edge[p].cap -= mi;
edge[edge[p].re].cap += mi;
ans += mi * edge[p].cost; // cost记录的为单位流量费用，必须得乘以流量。
}
flow += mi;
}
int nt, k;
void build()
{
init();
int w;
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);
}
void MCMF()
{
init();
build();
while(spfa()) end();
}
int main()
{
while(scanf("%d%d", &nt, &k) != EOF)
{
MCMF();
printf("%d\n", -ans);
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 5555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{
int v, cap, cost, next, re; // re记录逆边的下标。
} edge[MAXM];
int n,
补充：软件开发 , C++ ,
