欢迎访问~原文出处——

---

---

题意概括

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

---

 

题解

　　首先说两个概念：

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

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

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

　　有两个定理：

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

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

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

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

　　代码比较短。

---

 

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          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;}