Description

Input

Output

Sample Input

Sample Output

据说这题有两问，不过好像没数据，所以就去掉了（怪不得我都能看懂题解）

话说我完全不会二分图，更不会什么网络流，费用流（所以学习了简短的单纯形）

不过这道题真是道二分图好题（我什么都不懂！应该是我太弱了）

先学习了以下概念：引用自http://www.cnblogs.com/JoeFan/p/4324380.html

在有向无环图中，有如下的一些定义和性质：

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

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

那么很显然这道题就是求最长反链长度了。

一个定理：最长反链长度 = 最小链覆盖（用最少的链覆盖所有顶点）

对偶定理：最长链长度 = 最小反链覆盖  

所以这道题就是最小路径覆盖！（我是不会告诉你我还WA了十几发的）

#include <cstdio>
#include <cstring>
#define maxn 201
#define maxm 200001
using namespace std;
int h[maxm],last[maxm],head[maxn],from[maxn],a[maxn][maxn],l,b[maxn],ans;
void add(int x,int y)
{
	h[++l] = y;
	last[l] = head[x];
	head[x] = l;
}

int find(int x)
{
	for (int i = head[x];i;i = last[i])
	if (!b[h[i]])
	{
		b[h[i]] = 1;
		if ((!from[h[i]])||find(from[h[i]]))
		{
			from[h[i]] = x;
			return 1;
		}
	}
	return 0;
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y] = 1;
	}
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++)
			for (int k = 1;k <= n;k++)
				a[j][k] |= a[j][i]&a[i][k];
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++)
			if (i!=j&&a[i][j]) add(i,j+n);
	for (int i = 1;i <= n;i++)
	{
		memset(b,0,sizeof(b));
		if (find(i)) ans--;
    }
    ans += n;
    printf("%d",ans);
    return 0;
}