原題

Description

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

這片樹林里有N座房子，M條有向道路，組成了一張有向無環(huán)圖。

樹林里的樹非常茂密，足以遮擋視線，但是沿著道路望去，卻是視野開闊。如果從房子A沿著路走下去能夠到達B，那么在A和B里的人是能夠相互望見的。

現(xiàn)在cl2要在這N座房子里選擇K座作為藏身點，同時vani也專挑cl2作為藏身點的房子進去尋找，為了避免被vani看見，cl2要求這K個藏身點的任意兩個之間都沒有路徑相連。

為了讓vani更難找到自己，cl2想知道最多能選出多少個藏身點？

Input

第一行兩個整數(shù)N，M。

接下來M行每行兩個整數(shù)x、y，表示一條從x到y(tǒng)的有向道路。

Output

一個整數(shù)K，表示最多能選取的藏身點個數(shù)。

Sample Input

4 4

1 2

3 2

3 4

4 2

Sample Output

2

Data Constraint

對于20% 的數(shù)據(jù)，N≤10，M<=20 。

對于60% 的數(shù)據(jù) , N≤100，M<=1000 。

對于100% 的數(shù)據(jù)，N≤200，M<=30000，1<=x,y<=N 。

題解

• 算法：二分圖最小路徑覆蓋、floyd傳遞閉包

• 首先對讀入的有向圖做傳遞閉包（即 Floyd式的“最短路”，詳見下代碼）

• 然后求最小路徑覆蓋即可。最小路徑覆蓋數(shù)=n-最大匹配。

• 最大匹配用匈牙利算法，二分圖可用鄰接表存。

Code

#include<cstdio> #include<cstring> using namespace std; const int N=201; int a[N][N],f[N],ans; bool dis[N][N],bz[N]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; }//讀入優(yōu)化 inline bool find(int x) {for(int i=1;i<=a[x][0];i++)if (!bz[a[x][i]]){bz[a[x][i]]=true;if (!f[a[x][i]] || find(f[a[x][i]])){f[a[x][i]]=x;return true;}}return false; }//匈牙利算法 int main() {int n=read(),m=read();for(int i=1;i<=m;i++) dis[read()][read()]=true;//鄰接矩陣for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)if(dis[i][k])for(int j=1;j<=n;j++)if(dis[k][j]) dis[i][j]=true;//Floyd傳遞閉包for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][j]) a[i][++a[i][0]]=j;//鄰接表for(int i=1;i<=n;i++){memset(bz,false,sizeof(bz));if(find(i)) ans++;//最大匹配}printf("%d",n-ans);//頂點數(shù)-最大匹配return 0; }

請多多指教！

總結(jié)

以上是生活随笔為你收集整理的【NOIP2013模拟】Vani和Cl2捉迷藏 题解代码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。