最小费用最大流之 zkw费用流与普通费用流

这个是原作者的博文地址

这是今天刚学的，不过理解上还是很浅薄。最近发现算法不能融会贯通还是因为自己太死板了。

奉上一个基础版本的模板， POJ 2195 的代码。

本模板是不能直接用于任何有负权的图，更不能用于有负圈的情况

[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 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 += delta;
    return true;
}
void costflow()
{
    do
    {
        do
        {
            memset(vis, 0, sizeof(vis));
        }while(aug(src, INF));
    }while(modlabel());
}
int nt, m;
struct point
{
    int x, y;
}p[MAXN], h[MAXN];
int d[MAXN][MAXN];
char s[MAXN][MAXN];
int main()
{
    while(scanf("%d%d", &m, &nt) != EOF)
    {
        if(m == 0 && nt == 0) break;
        for(int i = 0; i < m; i++)
            scanf("%s", s[i]);
        int hcnt = 0, pcnt = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < nt; j++)
            {
                if(s[i][j] == 'H')
                {
                    hcnt++;
                    h[hcnt].x = i;
                    h[hcnt].y = j;
                }
                else if(s[i][j] == 'm')
                {
                    pcnt++;
                    p[pcnt].x = i;
                    p[pcnt].y = j;
                }
            }
        for(int i = 1; i <= pcnt; i++)
            for(int j = 1; j <= hcnt; j++)
                d[i][j] = abs(p[i].x - h[j].x) + abs(p[i].y - h[j].y);
        init();
        n = hcnt + pcnt + 2;

补充：软件开发 , C++ ,