行匹配列，然后枚举能够放“车”的位置，看看去掉这个位置再次求得的最大匹配会不会变小
#include <cstdio> #include <cstring> const int MAXN = 200; int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; int x[MAXN],y[MAXN]; int n,m,k; bool dfs(int u) { for(int v = 1;v <= m; ++v) { if(g[u][v] && !used[v]) { used[v] = true; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } } return false; } int hungary() { int res = 0; memset(linker,-1,sizeof(linker)); for(int i = 1; i <= n; ++i) { memset(used,false,sizeof(used)); if(dfs(i)) ++res; } return res; } int main() { int a,b,time = 0; while(scanf("%d %d %d",&n,&m,&k) != EOF) { memset(g,0,sizeof(g)); for(int i = 0; i < k; ++i) { scanf("%d %d",&x[i],&y[i]); g[x[i]][y[i]] = 1; } int maxPP = hungary(); int res = 0; for(int i = 0; i < k; ++i) { g[x[i]][y[i]] = 0; int temp = hungary(); if(temp < maxPP) ++res; g[x[i]][y[i]] = 1; } printf("Board %d have %d important blanks for %d chessmen.\n",++time,res,maxPP); } return 0; }