123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 |
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- const int MAXN = 110;
- bool Map[MAXN][MAXN];
- int link[MAXN];
- bool used[MAXN];
- int n,m,k;
- bool dfs(int u){
- for(int i = 1; i <= m; i++){
- if(Map[u][i] && used[i] == false ){
- used[i] = true;
- if(link[i] == -1 || dfs(link[i])){
- link[i] = u;
- return true;
- }
- }
- }
- return false;
- }
- int hungary(){
- memset(link,-1,sizeof(link));
- int ret = 0;
- for(int i = 1; i <= n; i++){
- memset(used,0,sizeof(used));
- if(dfs(i))ret++;
- }
- return ret;
- }
- int main(){
- int t = 0;
- while(~scanf("%d %d %d",&n,&m,&k)){
- memset(Map,0,sizeof(Map));
- for(int i = 1; i <= k; i++){
- int x,y;
- scanf("%d %d",&x,&y);
- Map[x][y] = 1;
- }
- int ans = hungary();
- int cnt = 0;
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= m; j++){
- if(Map[i][j] == 1){
- Map[i][j] = 0;
- if(ans > hungary())cnt++;
- Map[i][j] = 1;
- }
- }
- }
- printf("Board %d have %d important blanks for %d chessmen.\n",++t,cnt,ans);
- }
- }
|