- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- const int maxn = 1e4+5;
- int G[105][105];
- int a[maxn],b[maxn];
- int match[105];
- int st[105];
- int n,m,ans;
- bool find(int u) {
- for(int i = 1; i<=m; i++) {
- if(!st[i]&&G[u][i]) {
- st[i] = 1;
- if(!match[i]||find(match[i])) {
- match[i] = u;
- return true;
- }
- }
- }
- return false;
- }
- int Count() {
- int ans = 0;
- memset(match,0,sizeof(match));
- for(int i =0; i<=n; i++) {
- memset(st,0,sizeof(st));
- if(find(i))
- ans++;
- }
- return ans;
- }
- int main() {
- int k;
- int Case = 0;
- while(cin>>n>>m>>k) {
- memset(G,0,sizeof(G));
- for(int i = 0; i<k; i++) {
- cin>>a[i]>>b[i];
- G[a[i]][b[i]] = 1;
- }
- ans = 0;
- // 先求最大匹配
- int num = Count();
- // 然后依次去掉每一条边, 判断是不是会减少
- for(int i =0; i<k; i++) {
- G[a[i]][b[i]] = 0;
- if(Count()<num)
- ans++;
- G[a[i]][b[i]] = 1;
- }
- printf("Board %d have %d important blanks for %d chessmen.\n",++Case,ans,num);
- }
- }
来源: http://www.bubuko.com/infodetail-3447030.html