牛客多校第三场 B 题题解

B 题题意：$kk$ 个城市有 $nn$ 个人去上班，每个人选一个城市上班，第 $ii$ 个城市需要 $e_{i}e\_i$ 个人去上班。第 $ii$ 个人去第 $jj$ 个城市上班的代价为 $c_{i,j}c\_\{i,j\}$，问最小化代价。$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$，$k\le 10k\; \backslash leq\; 10$。

解法：如果不看范围，这题就是一个板子最小费用最大流——每个人向城市连边，流量为 $11$ 费用为 $c_{i,j}c\_\{i,j\}$；源点向每个人连边流量 $11$ 费用 $00$，第 $ii$ 个城市向汇点连边流量 $e_{i}e\_i$ 费用 $00$。

但是此题边数达到了 $1\times 10^{6}1\backslash times\; 10^6$，点数 $1\times 10^{5}1\backslash times\; 10^5$，因而考虑模拟费用流的过程。注意到每次费用流的过程为：从源点找到汇点找一条最短路径，然后更新本条路径的流量，更新反向边的流量。而这题每次增广的流量必然为 $11$，因而这极大的限制了运行效率。

首先考虑做第一步的优化，将人初始分到一些城市去，优化第一步的 $nn$ 次增广。一个简单的方法就是全部安排到 $11$ 号城市，利用 $\mathrm{n}\mathrm{o}\mathrm{w}\{\backslash rm\; now\}$ 数组来记录第 $ii$ 个人现在工作的城市。通过这一安排将源点到人所在的节点完全固定下来，节约了大量的无效增广。

接下来考虑人员的流动。显然从源点到人这一部分是不可能再去增广了，唯一能实现流的增广的就是让人从一个城市到另一个城市上班——因为此时 $11$ 号城市负载量过大，别的城市需要从 $11$ 号城市挖人。这样的好处是将原本人与城市之间复杂的边关系转化成了城市与城市之间的关系，由于 $kk$ 非常小因而这降低了大量的复杂度。

那么依次考虑可能的增广操作——第 $i,i\in [2,k]i,i\; \backslash in\; [2,k]$ 个城市需要进行 $e_{i}e\_i$ 次增广。对于这每一轮的增广，按照费用流的思想就是找到从源点到汇点的最短路，但是显然从源点到人、从城市到汇点这两部分对最短路是无意义的，因而考虑城市到城市之间的转移。对于每一对城市 $(u,v)(u,v)$，用一个堆记录之间所有可能的边——对于每个人 $ii$，若其原定城市为 $uu$，则 $(u,v)(u,v)$ 之间有一条距离为 $c_{i,v}-c_{i,u}c\_\{i,v\}-c\_\{i,u\}$ 的边，这个边代表了第 $ii$ 个人的跳槽选择。表示这个人从 $uu$ 城市换到了 $vv$ 城市所改变的代价。因而暴力使用 spfa 来找到一条从 $11$ 到 $ii$ 的路径。在松弛的时候只需要找到每一对城市中边权最小的一条边即可，使用优先队列维护。

注意：整个过程可以认为是 $11$ 号城市源源不断的给别的城市输送人，虽然其他城市之间也会互相换，但是这个换的意义是利用网络流中反悔边。所以源头一直都是 $11$。

找到最短路径之后就是费用流正常的操作——退流反向。这里的反向操作由于是在城市之间进行的，其意义是人在不同城市之间流动。例如对于一次增广中找到的路径 $u\to vu\; \backslash to\; v$，若其边代表的人是 $ii$，则意义是第 $ii$ 个人从第 $uu$ 个城市前往了 $vv$ 城市进行工作，因而更改 $\mathrm{n}\mathrm{o}\mathrm{w}\backslash rm\; now$ 数组。同时由于 $ii$ 的跳槽，他也有了新的 $k-1k-1$ 个跳槽选择，因而需要增设连向其他城市的 $k-1k-1$ 条边。

#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
using pli = pair<long long, int>;
priority_queue<pli, vector<pli>, greater<pli>> q[15][15];
//q[i][j] 内存储了边，这些边代表一个人的跳槽选择，以代价差为第一关键字，第二关键字仅用于表示人编号。
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> now(n + 1, 1), e(k + 1);//now[i]表示第i个人目前工作的城市
    for (int i = 1; i <= k;i++)
        scanf("%d", &e[i]);
    vector<vector<long long>> c(n + 1, vector<long long>(k + 1));
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= k;j++)
            scanf("%lld", &c[i][j]);
    long long ans = 0;
    for (int i = 1; i <= n;i++)
    {
        ans += c[i][1];
        for (int j = 2; j <= k;j++)
            q[1][j].emplace(c[i][j] - c[i][1], i);
    }
    queue<int> que;
    for (int i = 2; i <= k;i++)
        for (int times = 1; times <= e[i];times++)
        {
            vector<long long> dis(k + 1, inf);
            que.push(1);
            vector<int> pre(k + 1, 0), vis(k + 1, 0);
            vis[1] = 1;
            dis[1] = 0;
            while(!que.empty())
            {
                int tp = que.front();
                que.pop();
                vis[tp] = 0;
                for (int j = 2; j <= k;j++)
                {
                    while(!q[tp][j].empty() && now[q[tp][j].top().second] != tp)//当前人已经不在tp城市工作了，因而这条边废弃
                        q[tp][j].pop();
                    if (!q[tp][j].empty() && dis[j] > dis[tp] + q[tp][j].top().first)
                    {
                        dis[j] = dis[tp] + q[tp][j].top().first;
                        pre[j] = tp;
                        if(!vis[j])
                        {
                            vis[j] = 1;
                            que.push(j);
                        }
                    }
                }
            }
            ans += dis[i];
            int place = i;
            while(place != 1)
            {
                int fa = pre[place];
                int ori_id = q[fa][place].top().second;
                now[ori_id] = place;//退流表现为人工作城市的变化
                for (int i = 1; i <= k;i++)
                    if (i != place)//增设新的跳槽选择
                        q[place][i].emplace(c[ori_id][i] - c[ori_id][place], ori_id);
                place = fa;
            }
        }
    printf("%lld", ans);
    return 0;
}