题意
给定 DAG,问最多能选多少点,使任意两点间不连通
分析
考虑从路径上选点,要求每条路径只能选一个点,考虑可选路径和可选点数
- 记最小路径重复点覆盖为 $cnt$,则可选路径 $<= cnt$,则可选点数 $<= cnt$
- 下面构造一种选法,使点数可以等于 $cnt$
对于所有最小路径重复点覆盖中的路径,记终点集合为 $E$,从 $E$ 能到达的所有点记为 $nxt(E)$
- 若 $E \cap nxt(E) = \varnothing$,则 $E$ 内部两两之间不可相互到达,所以 $E$ 可以作为一种方案,点数为 $cnt$
- 若 $E \cap nxt(E) \neq \varnothing$,对 $E$ 中的所有点 $e_i$,让它一直往前走,直到 $e_i \notin nxt(E)$ 时选择当前点,则最终选出的 $cnt$ 个点可以作为一种方案
证明:对于任意 $e_i \in E$,最多走到起点,就能找到 $e_i \notin nxt(E)$
假设存在 $e_i \in E$,一直退到起点,路径上的点都属于 $nxt(E)$,则起点可以被其它终点到达,把两条路径首尾相接可合并为一条路径,使总路径数变少,这与最小路径重复点覆盖的定义矛盾
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 210, M = 30010;
int n, m;
bool d[N][N], st[N];
int match[N];
bool find(int x) {
for (int i = 1; i <= n; i ++)
if (d[x][i] && !st[i]) {
st[i] = 1;
int& bf = match[i];
if (!bf || find(bf))
return bf = x;
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
for (int a, b; m; m --)
scanf("%d%d", &a, &b), d[a][b] = 1;
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
d[i][j] |= d[i][k] & d[k][j];
int mch = 0;
for (int i = 1; i <= n; i ++) {
memset(st, 0, sizeof st);
if (find(i)) mch ++;
}
printf("%d\n", n - mch);
return 0;
}