分配问题

解题思路

有 $n$ 个人和 $n$ 件工作，每个人做每个工作都有不同的效率，将 $n$ 个工作分配给 $n$ 个人，问我们可以获得的最大效率和最小效率。

我们可以将 $n$ 个人看作左部节点，$n$ 个工作看作右部节点，这就是一个二分图。将每个人做对应工作的效率看作两个节点之间的边的权值，那么其实就是要我们求一个二分图的匹配，使得选中的所有边的权值和最大，这就是一个二分图最优匹配问题。

如果每条边上没有权值，单单是一个二分图最大匹配问题就非常简单，从源点向左部节点连边，右部节点向汇点连边，每个左部节点向每个右部节点连边，所有边的容量都是 $1$。这样的问题非常直观且常见，因此这里就不再证明原题的方案和流网络的可行流是一一对应的。

可以发现，任意一个可行方案都保证每个员工都能匹配一个工作，意味着任意一个可行方案对应到流网络中都是一个满流，即整数值最大流。

现在再加上每条边上有权值（效率），那么本题就是要我们在所有整数值最大流中找出权值和最大的一个流，就是最大费用最大流。

最大费用最大流只需要在 spfa 算法求最长增广路即可，最长路要求不能有正环，而二分图中不存在正环，因此不会有问题。

另外还要求最小费用最大流，不用再写一遍用 spfa 算法求最短增广路的 EK 算法，可以将所有边的费用取反，这样新图的最大费用最大流再取反回来就是原图的最小费用最大流。

注意，本题非常蛋疼的要求先输出最小费用，因此我们可以先求最小费用最大流，然后将所有边的费用取反去求最大费用最大流。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = 5210, INF = 0x3f3f3f3f;

int n, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], pre[N], incf[N]; //EK 算法需要的数组
bool st[N]; //spfa 算法需要的判重数组

void add(int a, int b, int c, int d) //添加边
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}

bool spfa() //判断是否存在最短增广路
{
    int hh = 0, tt = 1;
    q[0] = S;

    memset(d, 0x3f, sizeof d);
    d[S] = 0;

    memset(incf, 0, sizeof incf);
    incf[S] = INF;

    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(f[i] && d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(incf[t], f[i]);

                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}

int EK() //EK 算法求最小费用最大流
{
    int cost = 0;
    while(spfa())
    {
        int t = incf[T];
        cost += t * d[T];

        for(int i = T; i != S; i = e[pre[i] ^ 1])
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    //员工编号 1 ~ n，工作编号 n + 1 ~ 2 * n
    S = 0, T = n * 2 + 1; //源点、汇点
    for(int i = 1; i <= n; i++)
    {
        add(S, i, 1, 0); //从源点向所有员工连一条边，容量是 1，费用是 0
        add(n + i, T, 1, 0); //从所有工作向汇点连一条边，容量是 1，费用是 0
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            int x;
            scanf("%d", &x);
            add(i, n + j, 1, x); //从所有员工向所有工作连一条边，容量是 1，费用是对应的效率
        }

    printf("%d\n", EK()); //最小费用最大流

    //将所有边的流量清空，并将费用取反
    for(int i = 0; i < idx; i += 2)
    {
        f[i] += f[i ^ 1], f[i ^ 1] = 0;
        w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
    }

    printf("%d\n", -EK()); //最大费用最大流 = - 新图的最小费用最大流

    return 0;
}