题目：棋盘游戏
总结：这是用矩阵搞匈牙利算法。搞了半天
#include <stdio.h> #include <vector> #include <string.h> using namespace std; const int N = 1e2+5; const int M = 1e4+5; int c[M][2]; int g[N][N]; int n,m,k; int vis[M],pre[M]; bool dfs(int u){ for(int i = 1;i <= m;i++){ int v = g[u][i]; if(v&&!vis[i]){ vis[i] = 1; if(!pre[i] || dfs(pre[i])){ pre[i] = u; return true; } } } return false; } int solve(){ int ans = 0; memset(pre,0,sizeof pre); for(int i = 1;i <= n;i++){ memset(vis,0,sizeof vis); if(dfs(i)) ans++; } return ans; } int main(){ int t = 1; while(~scanf("%d%d%d",&n,&m,&k)){ memset(g,0,sizeof g); for(int i = 0;i < k;i++){ scanf("%d%d",&c[i][0],&c[i][1]); g[c[i][0]][c[i][1]] = 1; } int ans1 = solve(); // printf("%d\n",ans1); int ans2 = 0; for(int i = 0;i < k;i++){ g[c[i][0]][c[i][1]] = 0; int w = solve(); if(w < ans1){ ans2++; } g[c[i][0]][c[i][1]] = 1; } printf("Board %d have %d important blanks for %d chessmen.\n",t++,ans2,ans1); } return 0; }