一道最长反链的模板题
由 Dilworth 定理可知: 最小链覆盖数(偏序集能划分成的最少的全序集的个数) = 最长反链长度
其对偶定理: 最长链长度 = 最小反链覆盖数
(VFleaking 的证明: http://vfleaking.blog.163.com/blog/static/1748076342012918105514527/)
求解最小链覆盖的方式:
1, 先用 Floyd 求出传递闭包, 表示哪些 (x,y) 间是可以相互抵达的
2, 将每个点拆分, 最小链覆盖 = n - 二分图最大匹配
证明: 每匹配两个点, 则意味着少了一条链, 从而最少链的数量为 n - 最大匹配的数量
而先计算传递闭包是为了实现路径的可交叉, 相当于 "跳过" 交叉点进行匹配
- Code:
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN=105;
- int n,m,x,y,match[MAXN*2],f[MAXN][MAXN],vis[MAXN*2];
- bool dfs(int x)
- {
- for(int i=1;i<=n;i++)
- if(f[x][i] && !vis[i])
- {
- vis[i]=true;
- if(match[i]==-1 || dfs(match[i]))
- {
- match[i]=x;
- return true;
- }
- }
- return false;
- }
- int main()
- {
- cin>> n>> m;
- for(int i=1;i<=m;i++)
- cin>> x>> y,f[x][y]=1;
- for(int k=1;k<=n;k++)
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- f[i][j]|=f[i][k]&&f[k][j]&&!(i==j);
- memset(match,-1,sizeof(match));
- int res=n;
- for(int i=1;i<=n;i++)
- memset(vis,0,sizeof(vis)),res-=dfs(i);
- for(int i=1;i<=n;i++) cout << match[i] << " ";
- cout << endl;
- cout << res;
- return 0;
- }
- Review:
1, 最小链覆盖 (交叉 / 不交叉) 的求法
2, 记住将 i=j 的 f[i][j]设为 0
[BZOJ 1143] 祭祀 river
来源: http://www.bubuko.com/infodetail-2619313.html