BZOJ2718: [Violet 4]毕业旅行

时间：2021-11-02 06:13:42

2718: [Violet 4]毕业旅行

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 229  Solved: 126
[Submit][Status]

Description

BZOJ2718: [Violet 4]毕业旅行

Input

BZOJ2718: [Violet 4]毕业旅行

Output

最多可选多少景点

Sample Input

7 6
1 2
2 3
5 4
4 3
3 6
6 7

Sample Output

2

HINT

BZOJ2718: [Violet 4]毕业旅行

Source

题解：
同上一题
代码：
 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #define inf 1000000000

 #define maxn 110

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int p[maxn],n,m,f[maxn][maxn];

 bool v[maxn];

 bool find(int x)

 {

     for(int i=;i<=n;i++)

     if (f[x][i])

      if(!v[i])

      {

          v[i]=;

          if(!p[i]||find(p[i]))

          {

              p[i]=x;

              return ;

          }

      }

     return ;

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();m=read();

     int x,y;

     while(m--)x=read(),y=read(),f[x][y]=;

     for(int k=;k<=n;k++)

      for(int i=;i<=n;i++)

       for(int j=;j<=n;j++)

        f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);

     int ans=;

     for(int i=;i<=n;i++)

      {

          memset(v,,sizeof(v));

          if(find(i))ans++;

      }

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

     return ;

 }

相关文章