最小费用最大流之 zkw费用流与普通费用流 - c++编程基础

< MAXN; i ++)
{
dis[i] = INF;
vis[i] = false;
}
dis[src] = 0;
que[0] = src;
vis[src] = true;
while(t > h)
{
int u = que[h++];
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;
}
}
}
vis[u] = false;
}
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;
}
void build()
{

}
void MCMF()
{
init();
build();
while(spfa()) end();
}
int main()
{

return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-5
#define MAXN 555
#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 addEdge(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 < MAXN; i ++)
{
dis[i] = INF;
vis[i] = false;
}
dis[src] = 0;
que[0] = src;
vis[src] = true;
while(t > h)
{
int u = que[h++];
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;
}
}
}
vis[u] = false;
}
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;
}
void build()
{

}
void MCMF()
{
init();
build();
while(spfa()) end();
}
int main()
{

return 0;
}

最后来一个使用 Small Label First 优化

的 SPFA 来维护 zkw 算法中的距离标号, 保留多路增广

这也是根据原作者的程序改的，这个貌似就可以用负的边权了

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-5
#define MAXN 555
#define MAXM 55555
#define INF 100000007
using namespace std;
struct EDGE
{
int cost, cap, v;
int next, re;
}edge[MAXM];
int head[MAXN], e;
int vis[MAXN], d[M

最小费用最大流之 zkw费用流与普通费用流 (三)