题解 P2764 【最小路径覆盖问题】
Ireliaღ
2019-04-14 12:33:09
**最大流=最小割**
ISAP最大流+指针存图
## 建图
* 把原图每一个节点$i$拆成入点$i$和出点$i + n$，设超级源点为$0$，超级汇点为$n \times 2 + 1$
* 对于$\forall i \in [1, n]$，从$0$向$i$连边，容量$1$
* 对于$\forall i \in [1, n]$，从$i + n$向$n \times 2 + 1$连边，容量$1$
* 对于输入一条边$u \to v$，从$u$向$v + n$连边，容量$1$
## 输出
我们要找到**没被割掉并且是一条路径起点的点**，然后递归输出这条路径，具体见代码
最终路径数为$n - maxflow$
## 代码
```cpp
// luogu-judger-enable-o2
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 65;
const int MAXM = 6e3 + 5;
const int INF = 0x3f3f3f3f;
int n, m;
struct Edge{
int to, val;
Edge *nxt, *ops;
Edge(int to, int val, Edge *nxt): to(to), val(val), nxt(nxt) {}
};
namespace ISAP{
Edge *head[MAXN << 1], *cur[MAXN << 1];
int s, t, dep[MAXN << 1], gap[MAXN << 1], res;
void AddEdge(int u, int v, int w) {
head[u] = new Edge(v, w, head[u]);
head[v] = new Edge(u, 0, head[v]);
head[v]->ops = head[u]; head[u]->ops = head[v];
}
void Bfs() {
memset(dep, -1, sizeof(dep));
memset(gap, 0, sizeof(gap));
dep[t] = 0; gap[dep[t]]++;
queue<int> q; q.push(t);
while (!q.empty()) {
int u = q.front(); q.pop();
for (Edge *e = head[u]; e; e = e->nxt) {
int 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) {
res += flow;
return flow;
}
int used = 0;
for (Edge *e = head[u]; e; e = e->nxt) {
int v = e->to;
if (e->val && dep[v] == dep[u] - 1) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
e->val -= mi;
e->ops->val += mi;
used += mi;
}
if (used == flow) return used;
}
}
gap[dep[u]]--;
if (gap[dep[u]] == 0) dep[s] = n * 2 + 3;
dep[u]++;
gap[dep[u]]++;
return used;
}
void Work() {
res = 0;
Bfs();
while (dep[s] <= n << 1) Dfs(s, INF);
}
void Print(int u) {//输出路径
cout << u << ' ';
for (Edge *e = head[u]; e; e = e->nxt) {
int v = e->to;
if (e->val == 0 && v > n && v <= n << 1) {
Print(v - n);
return;
}
}
}
}
int main() {
ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
ISAP :: s = 0; ISAP :: t = n * 2 + 1;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
ISAP :: AddEdge(x, y + n, 1);
}
for (int i = 1; i <= n; i++) {
ISAP :: AddEdge(0, i, 1);
ISAP :: AddEdge(i + n, n * 2 + 1, 1);
}
ISAP :: Work();
/*for (Edge *e = ISAP :: head[0]; e; e = e->nxt) {
if (e->val == 0) ISAP :: Print(e->to), cout << endl;
}*/
//for (int i = 1; i <= n; i++) if (!nots[i]) ISAP :: Print(i), cout << endl;
for (int i = 1; i <= n; i++) {//找起点
bool ff = false;
for (Edge *e = ISAP :: head[i + n]; e; e = e->nxt) {
int v = e->to;
if (e->val && v >= 1 && v <= n) {
ff = true;
break;
}
}
if (!ff) ISAP :: Print(i), cout << endl;
}
cout << n - ISAP :: res << endl;
return 0;
}
```
~~反抄袭自寻~~