題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1281

解題思路：

把棋盤的行x看成二分圖左邊的點，列y看成二分圖右邊的點，那么就把可以放車的位置看成是一條邊，而二分圖的最大匹配中x互不相同，y互不相同，所以每個匹配都是不同行不同列，所以最大匹配就是最多可以放的車的數(shù)量。

接下來就是關鍵邊的查找了，這里實際可以每次刪一條邊，然后做二分匹配，看是否等于刪邊之前的最大匹配，如果是就說明剛剛刪除的那條邊并不影響增廣路的增加。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 105; int n,m,k,g[maxn][maxn]; int match[maxn],X[maxn],Y[maxn]; bool vis[maxn];bool dfs(int u) {for(int i = 1; i <= n; i++){if(g[u][i] > 0 && vis[i] == false){vis[i] = true;if(match[i] == -1 || dfs(match[i])){match[i] = u;return true;}}}return false; }int Max_Match() {int ans = 0;memset(match,-1,sizeof(match));for(int i = 1; i <= n; i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}return ans; }int main() {int cas = 1;while(scanf("%d%d%d",&n,&m,&k)!=EOF){memset(g,0,sizeof(g));for(int i = 1; i <= k; i++){scanf("%d%d",&X[i],&Y[i]);g[X[i]][Y[i]] = 1;}int ans = Max_Match(),cnt = 0;for(int i = 1; i <= k; i++){g[X[i]][Y[i]] = 0;int tmp = Max_Match();if(tmp < ans) cnt++;g[X[i]][Y[i]] = 1;}printf("Board %d have %d important blanks for %d chessmen.\n",cas++,cnt,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1281(二分图匹配+增广路)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。