bzoj1143-祭祀

题目

给出一个有向无环图，要在上面安放祭祀点。两个祭祀点必须不可达，求最多能安放多少个祭祀点。

分析

由于一条无法再延伸链上只能安放一个祭祀点，而我们要求的是最多能安放祭祀点的个数，所以要求的就是最长反链的长度。由Dilworth定理得出，最长反链长度=最小链覆盖数，所以问题就转化成了求最小链覆盖（最小路径覆盖）。

最小链覆盖

首先说明，最小链覆盖中一条链算一个，最小边覆盖中，一条链算上面的边数。

二分图中，最小边覆盖=\(n\)-最大匹配。

下面来证明这个等式。

为了让边覆盖最小，我们要让每条边每次覆盖的点数尽量多，最多每次新增两个点，即最大匹配中的情况。剩下没有覆盖的点，不可能再一次覆盖两个新的，只能连接到已有的匹配点，每次新覆盖一个点。所以得到最小边覆盖\(F=Match+(N-Match*2)=N-Match\)，分别表示原来的匹配边数和新增的边数。

那么在求解链覆盖问题的时候，我们可以把图拆点，转化成二分图，如果\(u\)与\(v\)有连边，那么就在二分图上连接\(u->v\prime\)。这样，二分图上的一个最小边覆盖就对应着原图上的一个最小链覆盖，因为我们可以首尾相连接成几条链。需要用floyd判断连通性。

代码

注意floyd部分的

if (f[i][k])

有时候可以大幅度提升时间效率，剪掉一些无用的情况。

#include<cstdio>

#include<cctype>

#include<cstring>

using namespace std;

int read() {

	int x=0,f=1;

	char c=getchar();

	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;

	for (;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int maxn=105;

bool a[maxn][maxn],alr[maxn];

int match[maxn],left[maxn],n;

bool dfs(int x) {

	for (int i=1;i<=n;++i) if (a[x][i] && !alr[i]) {

		alr[i]=true;

		if (!match[i] || dfs(match[i])) {

			match[i]=x;

			return true;

		}

	}

	return false;

}

int main() {

	#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

	#endif

	n=read();

	int m=read(),ans=0;

	while (m--) {

		int x=read(),y=read();

		a[x][y]=true;

	}

	for (int k=1;k<=n;++k) for (int i=1;i<=n;++i) if (a[i][k]) for (int j=1;j<=n;++j) if (a[k][j]) a[i][j]=true;

	for (int i=1;i<=n;++i) memset(alr,0,sizeof alr),ans+=dfs(i);

	printf("%d\n",n-ans);

}