3423. 【NOIP2013模拟】Vani和Cl2捉迷藏

Description

vani和cl2在一片树林里捉迷藏……

这片树林里有N座房子，M条有向道路，组成了一张有向无环图。

树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。如果从房子A沿着路走下去能够到达B，那么在A和B里的人是能够相互望见的。

现在cl2要在这N座房子里选择K座作为藏身点，同时vani也专挑cl2作为藏身点的房子进去寻找，为了避免被vani看见，cl2要求这K个藏身点的任意两个之间都没有路径相连。

为了让vani更难找到自己，cl2想知道最多能选出多少个藏身点？

Input

第一行两个整数N，M。

接下来M行每行两个整数x、y，表示一条从x到y的有向道路。

Output

一个整数K，表示最多能选取的藏身点个数。

Sample Input

4 4

1 2

3 2

3 4

4 2
           

Sample Output

2
           

Data Constraint

对于20% 的数据，N≤10，M<=20。

对于60% 的数据, N≤100，M<=1000。

对于100% 的数据，N≤200，M<=30000，1<=x,y<=N。

Solution

这题的转换思路是这样的：

首先我们要求这个DAG的最长反链长度。

反链的定义是：“反链（antichain）是一个偏序集S的子集，其中任意两个元素不可比较”

在这道题中具体来说就是：当两个点互不可见时，它们才能处于一条反链中。

根据Dilworth定理：

具体证明思路就是因为反链中每一个点根据定义都被一条不同的链所覆盖，

而整个图的链覆盖个数可能不止这么多条，所以推出

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

而我们可以分类讨论，用反证法（假设有点u不属于反链，根据题设推导）

推出最小链覆盖<=最长反链长度

那么就得出了 最小链覆盖=最长反链长度

可以看看这个博客的证明：

https://blog.csdn.net/qq_34564984/article/details/52993626

现在我们要做的就是求出这个图的最小链覆盖（可以相交的）

而最小链覆盖（不能相交的）=点数n-最大匹配数ans

证明就像这样：

我们假设有k条不相交的链覆盖了所有的点，长度（经过点数）分别为len1,len2……lenk

而每一条链所经过的边数数即为len1-1,len2-1……lenk-1

我们把它们加起来，因为覆盖了所有的点，所以len的和为 总点数n

而一条链在二分图中就对应着一个匹配，

（有可能是一堆小链拼成一条长链，比如1->2->3->4，匹配为 1-2 2-3 3-4）

所以它们的和为  总点数n-最大匹配数ans

最后一步就是把 最小链覆盖（可相交）转化为最小链覆盖（不可相交）

我们做一遍floyd传递闭包，就可以使一些本来会相交的路径分离开，比如说：

经过传递闭包后，就能使1和4  2和5直接相连，不再相交，这样就完成了转换。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define F(i,a,b) for(I i=a;i<=b;i++)
#define N 410
#define M 30010
using namespace std;
I n,m,x,y,ans,bz[N],ma[N],a[N][N];
I read(){
	I x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
I find(I x){
	F(i,1,n){
		if(a[x][i]&&!bz[i]){
			bz[i]=1;
			if(!ma[i]||find(ma[i])){
				ma[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
I main(){
	n=read();m=read();
	F(i,1,m){
		x=read();y=read();
		a[x][y]=1;
	}
	F(k,1,n)
		F(i,1,n)
			F(j,1,n){
				a[i][j]|=(a[i][k]&a[k][j]);
			}
	F(i,1,n){
		memset(bz,0,sizeof(bz));
		if(find(i)) ans++;
	}
	printf("%d\n",n-ans);
	return 0;
}
           

作者：zsjzliziyang 

QQ:1634151125 

转载及修改请注明 

本文地址:https://blog.csdn.net/zsjzliziyang/article/details/98112090