本文主要是介绍最小费用最大流之 zkw费用流与普通费用流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://www.artofproblemsolving.com/blog/54262
这个是原作者的博文地址
这是今天刚学的，不过理解上还是很浅薄。最近发现算法不能融会贯通还是因为自己太死板了。
奉上一个基础版本的模板， POJ 2195 的代码。
本模板是不能直接用于任何有负权的图，更不能用于有负圈的情况
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 222
#define MAXM 55555
#define INF 1000000007
using namespace std;
struct EDGE
{int cost, cap, v;int next, re;
}edge[MAXM];
int head[MAXN], e;
int vis[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()
{int delta = INF;for(int u = 1; u <= n; u++)if(vis[u])for(int i = head[u]; i != -1; i = edge[i].next)if(edge[i].cap && !vis[edge[i].v] && edge[i].cost < delta) delta = edge[i].cost;if(delta == INF) return false;for(int u = 1; u <= n; u++)if(vis[u])for(int i = head[u]; i != -1; i = edge[i].next)edge[i].cost -= delta, edge[edge[i].re].cost += delta;cost &这篇关于最小费用最大流之 zkw费用流与普通费用流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
