3423. 【NOIP2013模拟】Vani和Cl2捉迷藏 (Standard IO)

2024-01-13 12:13:52

Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits

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

Sample Output

Data Constraint

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

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

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

Source / Author: travel

题解：

需要用到Dilworth定理：

在一个偏序集中，最长反链长度 = 最小链覆盖链数（链不相交）

最小链覆盖链数为n（点数） - 最大匹配数。

要求匹配数，先用Floyd做一次传递闭包（因为Dilworth定理只在链不相交的情况下成立），再用匈牙利算法就行了。

偏序集：

并不是指一个集合，而是某一集合在一定的关系R下，可能成为偏序集。

A = {3 , 4 , 9 , 12}

关系R可以表示为一些数对的集合，{<3,9>,<3,12>,<4,12>}

可以发现在R中， <a,b> 满足 a | b。

这样还不能算，还要满足三个性质：

1.自反性。a|a;

2.对称性。a|b , b|a ,a=b

3. 传递性。 3|6 ， 6|12 ，那么3|12。

显然，在R下，A是偏序集。

传递闭包：

在集合X上的二元关系R的“传递闭包”是包含R的X上的最小的传递关系。

比如说关系R是点之间的到达， 1能到2 ， 2能到3，那么1能到3就是关系R的传递闭包。

其实就是求一个点是否能到另一个点。

f[i][j]=1表示i点能到j ， f[i][j] = 0反之。

这样题目中可以相交的链，就可以用求链不相交的算法（匈牙利）来做。

具体地， i和j之间没有直接连边，但如果f[i][j]=1则匈牙利可以跑。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mcy(a,b) memcpy(a,b,sizeof(a))
#pragma GCC optimize(3)
#define re register
#define inf 2000000000
#define N 210
#define M 30010
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;



int n,m,i,j,t,ans;
int l[N],len,f[N][N];
int bz[N]; // used
int get[N]; // who


void init()
{
	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];
}

int find(int x)
{
	for(int i=1;i<=n;i++) 
	if(i!=x && f[i][x] && bz[i]==0)
	{
		bz[i]=1;
		if(get[i]==0 || find(get[i]))
		{
			get[i] = x;
			return 1;
		} 
	}
	return 0;
}

int match()
{
	int tot=0;
	//find (i) 找与i匹配到的是谁 
	for(int i=1;i<=n;i++) 
	{	
		mem(bz,0);
		if(find(i)) ++ tot;
	}
	return tot;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++) 
	{
		int u,v;
		scanf("%d%d",&u,&v);
		f[u][v]=1;
	}
	init();
	
	ans = n - match();
	printf("%d",ans);
	return  0;
	
}

O极(n^3)

码农公寓

偏序集：

传递闭包 ：

相关文章

传递闭包：