POJ 2516 Minimum Cost KM算法 或者 最小费用最大流

这题还是挺裸的

当然 是用最小费最为方便。建图一目了然

KM麻烦那么一点，就是每个物品要拆成一份一份的。

建图的时候注意，KM匹配的模板一定是左边的点数不大于右边的点数 至少我的模板是这样的

在本题中，要求供应商提供的东西要满足商店的需求，不能满足就直接输出-1， 所以理论上商店的点应该比供应商少，商店的点应该放在左边，供应商放在右边

由于是最小权匹配，所以我这里用了一个比较大的数减去权值来处理，而不是直接取负数

先是一个最小费的

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 111
#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;
int shop[55][55], sup[55][55];
int money;
int main()
{
    while(scanf("%d%d%d", &nt, &m, &k) != EOF)
    {
        if(!nt && !m && !k) break;
        int res = 0;
        n = nt + m + 2;
        src = nt + m + 1;
        des = nt + m + 2;
        for(int i = 1; i <= nt; i++)
            for(int j = 1; j <= k; j++)
                scanf("%d", &shop[i][j]);
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= k; j++)
                scanf("%d", &sup[i][j]);
        int flag = 1;
        for(int q = 1; q <= k; q++)
        {
            init();
            for(int i = 1; i <= nt; i++)
                for(int j = 1; j <= m; j++)
                {
                    scanf("%d", &money);
                    add(j, i + m, INF, money);
                }
            int fk = 0;
            for(int i = 1; i <= m; i++)
                add(src, i, sup[i][q], 0);
            for(int i = 1; i <= nt; i++)
                add(i + m, des, shop[i][q], 0), fk += shop[i][q];
            while(spfa()) end();
            res += ans;
            if(flow != fk) flag = 0;
        }
        if(flag)
        printf("%d\n", res);
        else printf("-1\n");
    }
    return 0;
}

然后用KM做的

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 555
#define MAXM 55555
#define INF 100000007
using namespace std;
int n, m, ny, nx;
int w[MAXN][MAXN];
int lx[MAXN], ly[MAXN];
int linky[MAXN];
int visx[MAXN], visy[MAXN];
int slack[MAXN];
bool find(int x)
{
    visx[x] = 1;
    for(int y = 1; y <= ny; y++)
    {
        if(visy[y]) continue;
        int t = lx[x] + ly[y] - w[x][y];
        if(t == 0)
        {
            visy[y] = 1;
            if(linky[y] == -1 || find(linky[y]))
            {
                linky[y] = x;
                return true;
            }
        }
         else if(slack[y] > t) slack[y] = t;
    }
    return false;
}
int KM()
{
    memset(linky, -1, sizeof(linky));
    for(int i = 1; i <= nx; i++) lx[i] = -INF;
    memset(ly, 0, sizeof(ly));
    for(int i = 1; i <= nx; i++)
        for(int j = 1; j <= ny; j++)
            if(w[i][j] > lx[i]) lx[i] = w[i][j];

    for(int x = 1; x <= nx; x++)
    {
        for(int i = 1; i <= ny; i++) slack[i] = INF;
        while(true)
        {
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            if(find(x)) break;
            int d = INF;
            for(int i = 1; i <= ny; i++)
                if(!visy[i]) d = min(d, slack[i]);
            if(d == INF) return -1;
            for(int i = 1; i <= nx; i++)
                if(visx[i]) lx[i] -=d;
            for(int i = 1; i <= ny; i++)
                if(visy[i]) ly[i] += d;
                    else slack[i] -= d;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= ny; i++)
        if(linky[i] != -1) cnt++;
    if(cnt != nx) return -1;
    int tp = 0;
    for(int i = 1; i <= ny; i++)
        if(linky[i] != -1 ) tp += w[linky[i]][i] - 200;
    return -tp;
}
int nt, k;
int shop[55][55], sup[55][55];
int money[55][55];
int ha[555], hb[555];
int main()
{
    while(scanf("%d%d%d", &nt, &m, &k) != EOF)
    {
        if(!nt && !m && !k) break;
        for(int i = 1; i <= nt; i++)
            for(int j = 1; j <= k; j++)
                scanf("%d", &shop[i][j]);
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= k; j++)
                scanf("%d", &sup[i][j]);
        int flag = 1, res = 0;
        for(int q = 1; q <= k; q++)
        {
            memset(w, 0, sizeof(w));
            for(int i = 1; i <= nt; i++)
                for(int j = 1; j <= m; j++)
                    scanf("%d", &money[i][j]);
            nx = 0, ny = 0;
            for(int i = 1; i <= nt; i++)
                for(int j = 1; j <= shop[i][q]; j++)
                {
                    nx++;
                    ha[nx] = i;
                }
            for(int i = 1; i <= m; i++)
                for(int j = 1; j <= sup[i][q]; j++)
                {
                    ny++;
                    hb[ny] = i;
                }
            for(int i = 1; i <= nx; i++)
                for(int j = 1; j <= ny; j++)
                        w[i][j] = 200 - money[ha[i]][hb[j]];
            int tp = KM();
            if(tp == -1) flag= 0;
            else res += tp;
        }
        if(flag)
        printf("%d\n", res);
        else printf("-1\n");
    }
    return 0;
}