没有ISAP的题解,我来发一篇

题目大意

有很多题目和很多类型,每个题目可以对应多种类型,现在给出每种类型需要多少题目,输出方案

前置知识:ISAP算法

可以看pica学长的博客(哎?)

建图

一看,二分图匹配,于是我选择跑最大流较快的$ISAP$算法

(1) 首先把$0$当做超级源点,对从$1$到$n$每个题目建立容量为$1$的边

(2) 对于题目$i$如果可以属于$j$类型,那么从$i$到$n + j$建立容量为$1$的边

(3) 最后把$n + k + 1$当做超级汇点,对于类型$i$如果需要$x$道题,那么从$n + i$到$n + k + 1$建立容量为$x$的边,需要的总题数就是这些边的容量总和

$PS$:按照题目的输入顺序建图步骤应该是(1)(3)(2)

输出方案

以$0$为源点,$n + k + 1$为汇点跑$ISAP$最大流,如果最大流小于总题数,说明无法完成试卷安排,输出$No$ $Solution!$并结束程序。

遍历每个在$[n + 1, n + k]$的起点,遍历终点在$[1, n]$的边,也就是建图步骤(2)中建的反边,如果边权不为$0$,说明正边有流量,则选择了这组匹配,输出终点

代码

由于本人较懒,做网络流的题不愿意算最多需要多少条边,于是习惯采用指针动态开空间存图,$new$函数的速度较慢。但是由于加了当前弧优化的$ISAP$算法本身很快,即使是有耽误时间的$new$函数,也只跑了$30ms$,可见$ISAP$表现优异

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using std::queue;
using std::min;
using std::max;

const int MAXN = 1e4 + 5;
const int MAXK = 25;
const int INF = 0x3f3f3f3f;

int k, n;

struct Edge{
    int to, val;
    Edge *next, *opps;//需要记录反边指针
    Edge(int to, int val, Edge *next):to(to), val(val), next(next){};
};

Edge *head[MAXN + MAXK];

void AddEdge(int from, int to, int val) {
    head[from] = new Edge(to, val, head[from]);
    head[to] = new Edge(from, 0, head[to]);
    head[to]->opps = head[from]; head[from]->opps = head[to];
}

namespace ISAP{
    int dep[MAXN + MAXK], gap[MAXN + MAXK], maxflow = 0;
    int s, t;
    Edge *cur[MAXN + MAXK];

    void Bfs() {
        memset(dep, -1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        queue<int> q;
        dep[t] = 0; gap[0]++;
        q.push(t);
        int u, v;
        while (!q.empty()) {
            u = q.front(); q.pop();
            for (Edge *e = head[u]; e; e = e->next) {
                v = e->to;
                if (dep[v] != -1) continue;
                dep[v] = dep[u] + 1;
                gap[dep[v]]++;
                q.push(v);
            }
        }
    }

    int Dfs(int u, int flow) {
        if (u == t) {
            maxflow += flow;
            return flow;
        }
        int used = 0;
        for (Edge *&e = cur[u]; e; e = e->next) {//当前弧优化
            int v = e->to;
            if (e->val && dep[v] == dep[u] - 1) {
                int mi = Dfs(v, min(flow - used, e->val));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->opps->val += mi;
                }
                if (used == flow) return used;
            }
        }
        gap[dep[u]]--;
        if (gap[dep[u]] == 0) dep[s] = n + 1;
        dep[u]++;
        gap[dep[u]]++;
        cur[u] = head[u];//复原当前弧
        return used;
    }
    void Work() {
        for (int i = 0; i <= n + k + 1; i++) cur[i] = head[i];
        maxflow = 0;
        Bfs();
        while (dep[s] < n) Dfs(s, INF);
    }
    void OutPut() {
        for (int i = 1; i <= k; i++) {
            printf("%d: ", i);
            for (Edge *e = head[n + i]; e; e = e->next) {//遍历反边输出匹配
                int v = e->to;
                if (v >= 1 && v <= n && e->val) printf("%d ", v);
            }
            putchar('\n');
        }
    }
}

int main() {
    memset(head, 0, sizeof(head));
    scanf("%d %d", &k, &n);
    ISAP::s = 0; ISAP::t = n + k + 1;//记录超级源点汇点
    int m = 0;
    for (int i = 1; i <= n; i++) AddEdge(0, i, 1);//建图步骤(1)
    for (int i = 1, x; i <= k; i++) {//建图步骤(3)
        scanf("%d", &x);
        m += x;
        AddEdge(n + i, n + k + 1, x);
    }
    for (int i = 1, p; i <= n; i++) {//建图步骤(2)
        scanf("%d", &p);
        for (int j = 1, x; j <= p; j++) {
            scanf("%d", &x);
            AddEdge(i, n + x, 1);
        }
    }
    ISAP::Work();//跑最大流
    if (ISAP::maxflow < m) return printf("No Solution!") & 0;//压行(雾)+特判
    ISAP::OutPut();//输出方案
    return 0;
}
/*
3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3
*/