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