HDU 2458 Kindergarten[二分圖之反建邊]

題意：………… 思路：反鍵邊求最小點集覆蓋key，boys+girls-key 就是答案。根據題意：反建邊後，每條邊代表的是該男孩和該女孩不認識，求的最小點集，把這些點去掉後即所有反建的邊被去掉，則剩余的就是男女之間都相互認識。。 AC代碼： [cpp]  #include<iostream>   #include<cstdio>   #include<cstring>   using namespace std;   const int Max = 300;   bool use[Max];   int link[Max];   bool map[Max][Max];   void init()   {       memset(map,true,sizeof(map));   }   bool Dfs(int k,int m)   {       int i,j;       for(i=1;i<=m;i++)       {           if(map[k][i]&&use[i])           {               use[i] = false;               if(!link[i]||Dfs(link[i],m))               {                   link[i] = k;                   return true;               }           }       }       return false;   }   int MaxMatch(int n,int m)   {       int i,j;       int ans = 0;       memset(link,0,sizeof(link));       for(i=1;i<=n;i++)       {           memset(use,true,sizeof(use));           if(Dfs(i,m))               ans++;       }       return ans;   }   int main()   {       int i,j,n,m,k;       int ncase = 1;       while(scanf("%d%d%d",&n,&m,&k)&&(n+k+m))       {           init();           while(k--)           {               scanf("%d%d",&i,&j);               map[i][j] = false;           }           printf("Case %d: ",ncase++);           printf("%d\n",n+m-MaxMatch(n,m));       }       return 0;   }