欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 – BZOJ1143

题意概括

　　给出一个有向图。求最小链覆盖。

题解

　　首先说两个概念：

　　　　链：一条链是一些点的集合，链上任意两个点x, y，满足要么 x 能到达 y ，要么 y 能到达 x 。

　　　　反链：一条反链是一些点的集合，链上任意两个点x, y，满足 x 不能到达 y，且 y 也不能到达 x。

　　这题就是求最长反链长度。

　　有两个定理：

　　最长反链长度 = 最小链覆盖

　　最长链长度 = 最小反链覆盖

　　这题明显可以使用第一个。

　　那么只需要floyd跑一跑，然后二分图匹配就可以了。

　　代码比较短。

代码

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=100+5,N2=N*2;
int n,m,match[N2];
bool g[N][N],g2[N2][N2],vis[N2];
bool dfs(int x){
for (int i=1;i<=n;i++){
int y=i+n;
if (!vis[y]&&g2[x][y]){
vis[y]=1;
if (match[y]==-1||dfs(match[y])){
match[y]=x;
return 1;
}
}
}
return 0;
}
int main(){
memset(g,0,sizeof g);
memset(g2,0,sizeof g2);
scanf("%d%d",&n,&m);
for (int i=1,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
g[a][b]=1;
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=g[i][j]||(g[i][k]&&g[k][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (g[i][j])
g2[i][j+n]=1;
int cnt=0;
memset(match,-1,sizeof match);
for (int i=1;i<=n;i++){
memset(vis,0,sizeof vis);
if (dfs(i))
cnt++;
}
printf("%d\n",n-cnt);
return 0;
}