[bzoj1143]-[CTSC2008]祭祀river

题目（BZOJ）
这题先看数据范围：n<=100，可以用floyd来求个传递闭包。
然后跑二分图最大匹配，用总点数减去最大匹配数就是答案。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,m;
int a[205];
int f[205];
bool dis[105][105];
int idx;
int ans;
struct edge{
	int vk;
	int nxt;
}e[5005];
int t,head[205];
void ad(int u,int v)
{
	e[++t].vk=v;
	e[t].nxt=head[u];
	head[u]=t;
}
bool find(int u)
{
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (f[v]!=idx)
		{
			f[v]=idx;
			if (!a[v] || find(a[v]))
			{
				a[v]=u;
				return true;
			}
		}
	}
	return false;
}
inline void floyd()
{
	for (int k=1;k<=n;++k)
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				if (i!=j && i!=k && j!=k)
					dis[i][j]=(dis[i][j] || (dis[i][k] && dis[k][j]));
}
int main()
{
	scanf(
	for (int i=1;i<=m;++i)
	{
		int x,y;
		scanf(
		dis[x][y]=1;
	}
	floyd();
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
		{
			if (i!=j)
			{
				if (dis[i][j])
				{
					ad(i,j);
				}
			}
		}
	ans=n;
	for (int i=1;i<=n;++i)
	{
		++idx;
		if (find(i)) ans--;
	}
	printf(
	return 0;
}