题面

题面

思路

一眼的费用流模型，建立超级源点S连向所有的科目，容量为该科目份数，费用为0，建立超级汇点T，将所有人连向超级汇点，容量为人最多做的份数，费用为0，将第i个题目连向第j个人，容量为\infty，花费就是题目里的c_{i,j}。至于为什么这样连，我把样例对应的网络放在下面，你可以对着图模拟，然后就能明白对应的容量和费用的意义了。（括号中第一个数是容量，第二个数是费用。注：将人连向题目与这种构图方法是等价的，没有太大区别）：

样例
红红火火恍恍惚惚，这道题就这样切掉了，诶等等为什么超时？
超时啦
让我们冷静分析一波复杂度吧！
众所周知，EK算法的复杂度是O(nm^2)的，在这题变态的构图下，m达到顶峰即m=n^2，复杂度就炸成O(n^5)，这要怎么破？
现在超级无敌望尘莫及令人望其项背的神奇优化——动态加边登场啦！

动态加边的基本思路是：一开始只加入一部分边进行增广，如果某些边满流，就继续往里面加边，不断这样做。

对于这道题：我们用数组E[i]存下与左边第i个点与右边所有的点所连的边，对每个E[i]按照花费从小到大排序。先把左边每个点i的E[i]中花费最小的边加进图，然后跑EK。记E[i][j].to表示i的第j条边所连接的右边的点，E[i][j].dist表示i的第j条边的花费，cnt[i]表示i上一次加进去的是第几条边。接着检查左边每个点i，如果E[i][cnt[i]].to连向T的边满流时，我们必须添加新边，不然有可能无法增广。于是就从cnt[i]开始从小到大加边，一直到E[i][cnt[i]].to连向T的边没有满流或者已经全部加完为止。加完以后继续跑EK。

至于这样为什么能够提高效率。你可以这样理解吧（实在是想不到好的数学证明了），我们是按照从小到大的顺序加边，所以S到T的最短路更有可能在边数较少的情况下找到，这样效率就可以提高。并且这样的加边顺序令后面所加的边对最短路的影响较小，使bfs的过程效率提高。程序运行时间就-1500ms了(笑)。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
inline int read()
{
    int x = 0, f = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = 1;
    for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ '0');
    return f ? -x : x;
}
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }

typedef long long ll;
const int N = 2e2 + 7, INF = 0x3f3f3f3f;

struct edge { int to, dist; } c[N][N];
int cnt[N], edgepre[N];
int cmp(edge p, edge q) { return p.dist < q.dist; }

int n, m, a[N], b[N];
int tot = 1, st[N * 20], to[N * N * 20], nx[N * N * 20], len[N * N * 20];
ll ans, cost[N * N * 20];

inline void add(int u, int v, int w, int c)
{
    to[++tot] = v, nx[tot] = st[u], len[tot] = w, cost[tot] = c, st[u] = tot;
    to[++tot] = u, nx[tot] = st[v], len[tot] = 0, cost[tot] = -c, st[v] = tot;
}

ll dis[N * 20];
int head, tail, que[N * 10000], vis[N * 20], maxflow[N * 20], pre[N * 20], S, T;
int bfs()
{
    head = 1, tail = 0;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(pre, 0, sizeof(pre));
    memset(maxflow, 0, sizeof(maxflow));
    dis[S] = 0, que[++tail] = S, vis[S] = 1, maxflow[S] = INF;
    while (head <= tail)
    {
        int u = que[head++];
        vis[u] = 0;
        for (int i = st[u]; i; i = nx[i])
        {
            int v = to[i];
            if (len[i] > 0 && dis[u] + cost[i] < dis[v])
            {
                maxflow[v] = min(maxflow[u], len[i]), dis[v] = dis[u] + cost[i], pre[v] = i;
                if (!vis[v]) que[++tail] = v, vis[v] = 1;
            }
        }
    }
    return maxflow[T];
}

void solve()
{
    while (bfs())
    {
        int now = T;
        while (now) len[pre[now]] -= maxflow[T], len[pre[now] ^ 1] += maxflow[T], now = to[pre[now] ^ 1];
        for (int i = 1; i <= n; i++)
            while (!len[edgepre[c[i][cnt[i]].to]] && cnt[i] < m)
                cnt[i]++, add(i, c[i][cnt[i]].to + n, INF, c[i][cnt[i]].dist);
        ans += maxflow[T] * dis[T];
    }
    printf("%lld\n", ans);
}

void make_graph()
{
    S = 0, T = n + m + 1;
    for (int i = 1; i <= n; i++) add(S, i, a[i], 0);
    for (int i = 1; i <= m; i++) add(i + n, T, b[i], 0), edgepre[i] = tot - 1;
    for (int i = 1; i <= n; i++)
    {
        sort(c[i] + 1, c[i] + m + 1, cmp);
        add(i, c[i][1].to + n, INF, c[i][1].dist);
        cnt[i] = 1;
    }
}

void init()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= m; i++) b[i] = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            c[i][j].dist = read(), c[i][j].to = j;
}

int main()
{
    init();
    make_graph();
    solve();
    return 0;
}