(step6.3.5)hdu 1281(棋盘游戏——二分图的完美匹配)

题目大意:本体是中文题。读者可以直接在OJ上看

解题思路:

1)完美匹配:所有的端点都是匹配点

2)对于二分图的完美匹配，我们需要用一个数组来存储匹配点。(而二分图的其他问题（我们则可以直接使用变量来存储即可)

/* * 1281_1.cpp * *  Created on: 2013年8月31日 *      Author: Administrator */#include <iostream>using namespace std;const int maxn = 101;int map[maxn][maxn];int link[maxn];bool useif[maxn];int n,m;int can(int t){int i;for(i = 1 ; i <= m ; ++i){if(useif[i] == 0 && map[t][i]){useif[i] = 1;if(link[i] == -1 || can(link[i]) ){link[i] = t;return 1;}}}return 0;}int max_match(){int i;int num = 0;memset(link,-1,sizeof(link));for(i = 1 ; i <= n ; ++i){memset(useif,0,sizeof(useif));if(can(i)){num++;}}return num;}int main(){int k;int counter = 1;while(scanf("%d%d%d",&n,&m,&k)!=EOF){int i;int a[k+1],b[k+1];memset(map,0,sizeof(map));memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i = 1 ; i <= k ; ++i){//int a,b对于完美匹配的题,需要用数组记录下匹配点。假如不是完美匹配的二分图的题。直接用a,b即可scanf("%d%d",&a[i],&b[i]);map[a[i]][b[i]] = 1;}int num = max_match();int count = 0;for(i = 1 ; i <= k ; ++i){map[a[i]][b[i]] = 0;int d = max_match();map[a[i]][b[i]] = 1;if(d != num){//如果d!=num,则说明该点是匹配点.count++;}}printf("Board %d have %d important blanks for %d chessmen.\n",counter++,count,num);}}