二分图——最大不可互相到达数 = 最小路径覆盖数-白红宇

二分图——最大不可互相到达数 = 最小路径覆盖数

阅读量：4956 次

发布时间：2019-06-12

本文共 1581 字，大约阅读时间需要 5 分钟。

study from:

https://blog.csdn.net/winter2121/article/details/79849472

https://nanti.jisuanke.com/t/19979

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
             9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #include 
                   
                    16 #include 
                    
                     17 using namespace std;18 #define ll long long19 #define minv 1e-620 #define inf 1e921 #define pi 3.141592653622 #define nl 2.718281828423 const ll mod=1e9+7;//99824435324 const int maxn=1e2+10;25 26 bool vis[maxn];27 int cony[maxn],r[maxn][maxn],n;28 29 bool dfs(int x)30 {31 int y;32 for (y=1;y<=n;y++)33 if (!vis[y] && r[x][y])34 {35 vis[y]=1;36 if (cony[y]==0 || dfs(cony[y]))37 {38 cony[y]=x;39 return 1;40 }41 }42 return 0;43 }44 45 int main()46 {47 int sum,t,m,i,j,k,x,y;48 scanf("%d",&t);49 while (t--)50 {51 scanf("%d%d",&n,&m);52 memset(r,0,sizeof(r));53 for (i=1;i<=m;i++)54 {55 scanf("%d%d",&x,&y);56 r[x][y]=1;57 }58 59 for (k=1;k<=n;k++)60 for (i=1;i<=n;i++)61 for (j=1;j<=n;j++)62 r[i][j]|=r[i][k]&r[k][j];63 64 sum=n;65 memset(cony,0,sizeof(cony));66 for (i=1;i<=n;i++)67 {68 memset(vis,0,sizeof(vis));69 sum-=dfs(i);70 }71 printf("%d\n",sum);72 }73 return 0;74 }