1 /*--------------------------------------------------------------------------------------*/  2   3 #include <algorithm>  4 #include <iostream>  5 #include <cstring>  6 #include <ctype.h>  7 #include <cstdlib>  8 #include <cstdio>  9 #include <vector> 10 #include <string> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <set> 15 #include <map> 16  17 //debug function for a N*M array 18 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++) 19 {for(int j=0;j<(M);j++){ 20 printf("%d",G[i][j]);}printf("\n");} 21 //debug function for int,float,double,etc. 22 #define debug_var(X) cout<<#X"="<<X<<endl; 23 #define LL long long 24 const int INF = 0x3f3f3f3f; 25 const LL LLINF = 0x3f3f3f3f3f3f3f3f; 26 /*--------------------------------------------------------------------------------------*/ 27 using namespace std; 28  29 int N,M,E,T; 30 const int maxn = 1000; 31 vector <int> G[maxn]; 32 int uN; 33 int Mx[maxn],My[maxn]; 34 int dx[maxn],dy[maxn]; 35 int dis; 36 bool used[maxn]; 37 bool searchP() 38 { 39     queue<int> Q; 40     dis = INF; 41     memset(dx,-1,sizeof dx); 42     memset(dy,-1,sizeof dy); 43     for(int i=1;i<=uN;i++) 44     { 45         if(Mx[i] == -1) 46         { 47             Q.push(i); 48             dx[i] = 0; 49         } 50     } 51     while(!Q.empty()) 52     { 53         int u = Q.front(); 54         Q.pop(); 55         if(dx[u] > dis) break; 56         int sz = G[u].size(); 57         for(int i=0;i<sz;i++) 58         { 59             int v = G[u][i]; 60             if(dy[v] == -1) 61             { 62                 dy[v] = dx[u] + 1; 63                 if(My[v] == -1) dis = dy[v]; 64                 else 65                 { 66                     dx[My[v]] = dy[v] + 1; 67                     Q.push(My[v]); 68                 } 69             } 70         } 71     } 72     return dis != INF; 73 } 74 bool DFS(int u) 75 { 76     int sz = G[u].size(); 77     for(int i=0;i<sz;i++) 78     { 79         int v = G[u][i]; 80         if(!used[v] && dy[v] == dx[u]+1) 81         { 82             used[v] = true; 83             if(My[v] != -1 && dy[v] == dis) continue; 84             if(My[v] == -1 || DFS(My[v])) 85             { 86                 My[v] = u; 87                 Mx[u] = v; 88                 return true; 89             } 90         } 91     } 92     return false; 93 } 94 int MaxMatch() 95 { 96     int res = 0; 97     memset(Mx,-1,sizeof Mx); 98     memset(My,-1,sizeof My); 99     while(searchP())100     {101         memset(used,false,sizeof used);102         for(int i=1;i<=uN;i++)103         {104             if(Mx[i] == -1 && DFS(i)) res++;105         }106     }107     return res/2;108 }109 110 vector <pair<int,int> > save;111 set <pair<int,int> > st;112 int cas;113 int main()114 {115     while(~scanf("%d%d%d",&N,&M,&E))116     {117         uN = N+M;118         for(int i=0;i<maxn;i++) G[i].clear();119         save.clear();120         for(int i=0,a,b;i<E;i++)121         {122             scanf("%d%d",&a,&b);123             G[a].push_back(N+b);124             G[N+b].push_back(a);125             save.push_back(make_pair(a,N+b));126         }127 128         st.clear();129         int match = MaxMatch();130         //printf("MaxMatch:%d\n",match);131         for(int i=1;i<=N;i++)132         {133             if(Mx[i] != -1) st.insert(make_pair(i,Mx[i]));134         }135         int imp = 0;136         for(auto it = st.begin();it != st.end();it++)137         {138             pair<int,int> cur = *it;139             //printf("delete [%d,%d]\n",cur.first,cur.second);140             for(int i=0;i<maxn;i++) G[i].clear();141             for(int i=0;i<save.size();i++) if(save[i] != cur)142             {143                 int a = save[i].first,b = save[i].second;144                 G[a].push_back(b);145                 G[b].push_back(a);146             }147             if(MaxMatch() < match) imp++;148         }149         printf("Board %d have %d important blanks for %d chessmen.\n",++cas,imp,match);150     }151 }