前些日子WCMG给我（蒟蒻）们上过二分图，也讲了这道题，然而课上晕头转向，并没有搞清楚什么，这次认真学习了然而并没有什么卵用

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1143

题目大意：给出一个DAG，求出其最大点独立集（集合间任意两点不联通）

根据foreseeable大爷的课件，此问题可以转化为求改图的最小可相交路径覆盖。（下文会解释为什么）

我们可以先讨论一下如何求出改图的最小不可相交路径覆盖，可以讲图上的点u拆为(u,u')，对于任意边(u,v),则连接(u,v')，形成一个二分图，在上面跑二分图匹配，可得，最小路径覆盖数＝G的点数－最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。

所以又可以得到最小路径覆盖数＝G的点数－二分图最大匹配数。而如果如果要求的是可相交路径覆盖，只需要预处理时用floyd得到两点间联通性然后手动加边即可。

下面再来填一下一开始的坑，为什么此问题可以转化为求改图的最小可相交路径覆盖。foreseeable大爷的课件上明明白白地写着dilworth定理，并写了一些介绍： 偏序集最大独立集（最长反链）＝最小链覆盖大小，然而这个公式我却根本看不懂，什么偏序集，什么反链，是该科普一下。

1. 偏序集：（可自行参看wikipedia）。而foreseeable大爷对其进行了简单说明：什么是偏序关系:具有自反性，反对称性，传递性的一种关系。(更严谨定义请看组合数学类的书)
2. 链:一个集合,集合中的任意数可比。
3. 反链：一个集合，集合中任意的两数均不可以比较。

• dilworth定理:最长反链＝最小链覆盖的大小（其对偶定理：最长链＝最小反链覆盖的大小）
• 首先，我们假设偏序集X最长反链长度为p,最小链覆盖为r。
• 因为反链内的任意两点不可比，所以它们肯定出现于不同的链中，所以r≤p。
• 接下来我们分为两种情况进行考虑

1. ​最长反链为最小元的集合或是最大元的集合或两者都是，那么我们可以取出一个最小元x和一个对应最大元y，然后通过归纳假设，可得偏序集X-{x,y}的最小链覆盖为r-1,加上x,y所形成的边覆盖，形成共有r条边的覆盖
2. 最长链既不为最小元的集合也不为最大元的集合，此时设这个最长链为A，并定义一下两个集合：

可以得到如下性质:

然后我们可以使用归纳假设法，得到A+和A-都可以被划分为r个链，并且这些链的起点和终点分别都在A上，所以可以将A+和A-中的不同的链经过共同点而相连，最终形成覆盖的r条链。

贴上代码（学会了floyd的正确写法 = =）

#include <iostream>
#include <cstdio>
#define maxn 110
using namespace std;

int n,m,ind,ans,tot;
bool f[maxn][maxn];
int state[maxn],p[maxn],fir[maxn];
int b[maxn*maxn],nex[maxn*maxn];

int read(){
	int x=0,f=1; char ch=getchar();
	while (ch>'9'||ch<'0'){ if (ch=='-') f=-1; ch=getchar();}
	while (ch<='9'&&ch>='0'){ x=x*10+ch-'0'; ch=getchar();}
	return x*f;
}
void add(int x, int y){
	b[++tot]=y; nex[tot]=fir[x]; fir[x]=tot;
}
bool hungray(int x){
	for (int u=fir[x]; u; u=nex[u]){
		if (state[b[u]]!=ind){
			state[b[u]]=ind;
			if (p[b[u]]==0||hungray(p[b[u]])){
				p[b[u]]=x;
				return 1;
			} 
		}
	}
	return 0;
}
int main(){
	n=read(); m=read();
	for (int i=1; i<=m; i++){
		int x=read(); int y=read();
		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];
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++)
			if (f[i][j]) add(i,j);
	}
	ans=0; ind=1;
	for (int i=1; i<=n; i++){
		ind++;
		if (hungray(i)) ans++;
	}
	printf("%d",n-ans);
	return 0;
}

Fractal128