这题水很深...
题目给了一个有向无环图, 要求找出最多的点且这些点中不存在两个点使得它们之间有路径
如果 $x$ 能到 $y$, 那么 $x,y$ 只能选其中一个, 所以连上一条边 $(x,y)$ 不改变答案(其实是在找传递闭包)
这时可以转化一下题目: 给出一个偏序集, 问最大反链长度
Dilworth 定理: 偏序集的最大反链长度 = 偏序集划分为链的最少链数
这里有一篇博客写得非常好, 这里引用 + 删减
用数学归纳法
假设偏序集为 $S$ 且 $n=\left|S\right|$, 对于 $n\geq 2$, 假设对所有的 $m\lt n$ 命题成立
取出 $S$ 中的一个极大元 $x$, 令 $S=S-\left\{x\right\}$
对于 $S$, 命题成立, 假设它被划分成 $k$ 条链, 取 $B$ 为每条链的最大元组成的偏序集, 它是一个最大反链
若 $x$ 与 $B$ 中任一元素不可比, 那么它使最少链数 $+1$, 使最大反链长度 $+1$
若 $x$ 与 $B$ 中某一元素可比, 因为是极大元, 所以它不改变最少链数和最大反链长度
所以我们成功地把问题转化为求最小链划分
求偏序集的最小链划分是一个经典问题, 可以参考这篇博客, 这里引用 + 删减
把每个点 $x$ 拆成 $\left(x_1,x_2\right)$, 对于每条原图中的边 $(x,y)$, 在新图中连边 $\left(x_1,y_2\right)$
设 $match$ 为新图的最大匹配数, 答案 $=n-match$
原理是匹配一条边相当于连接两条链 (答案 $-1$), 因为是划分(链不可相交) 所以对应到新图中匹配边不可相交
然后就做完了
总的过程: 先用 Warshall 算法求出传递闭包, 再建二分图用匈牙利算法跑匹配, 答案是节点数减去匹配数
代码很短, 但背后蕴含的思想较为恐怖
原来离散数学前几章不是一点用都没有啊
- #include < stdio.h > #include < string.h > bool g[110][110],
- v[110];
- int n,
- link[110];
- bool hungary(int x) {
- for (int i = 1; i <= n; i++) {
- if (g[x][i] && !v[i]) {
- v[i] = 1;
- if (link[i] == -1 || hungary(link[i])) {
- link[i] = x;
- return 1;
- }
- }
- }
- return 0;
- }
- int match() {
- int i,
- s = 0;
- memset(link, -1, sizeof(link));
- for (i = 1; i <= n; i++) {
- memset(v, 0, sizeof(v));
- if (hungary(i)) s++;
- }
- return s;
- }
- int main() {
- int m,
- i,
- j,
- k;
- scanf("%d%d", &n, &m);
- while (m--) {
- scanf("%d%d", &i, &j);
- g[i][j] = 1;
- }
- for (k = 1; k <= n; k++) {
- for (i = 1; i <= n; i++) {
- for (j = 1; j <= n; j++) g[i][j] = g[i][j] || (g[i][k] && g[k][j]);
- }
- }
- printf("%d", n - match());
- }
来源: http://www.bubuko.com/infodetail-2507586.html