题解 P2763 【试题库问题】
Ireliaღ
2019-02-03 13:16:24
## 没有ISAP的题解，我来发一篇
### 题目大意
有很多题目和很多类型，每个题目可以对应多种类型，现在给出每种类型需要多少题目，输出方案
### 前置知识：ISAP算法
可以看~~pica~~学长的[博客](https://www.cnblogs.com/ubospica/p/9974285.html)（哎?）
### 建图
一看，二分图匹配，于是我选择跑最大流较快的$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$表现优异
```cpp
#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
*/
```