本文主要是介绍hdu1281 二分图匹配_必要边，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。所以现在Gardon想让小希来解决一个更难的问题，在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？
#include <iostream>
#include <string.h>
#include <cstdio>using namespace std;const int MAXN = 100 + 10;
int n, m, k;int c[MAXN][MAXN];
int match[MAXN];
bool vis[MAXN];bool dfs(int u)
{for (int i = 1; i <= m; i++){if (!vis[i] && c[u][i]){vis[i] = true;if (match[i] == -1 || dfs(match[i])){match[i] = u;return true;}}}return false;
}int solve()
{int res = 0;memset(match, -1, sizeof(match));for (int i = 1; i <= n; i++){memset(vis, false, sizeof(vis));if (dfs(i)){res++;}}return res;
}void input()
{int cases = 0;while (cin >> n >> m >> k){int u, v;memset(c, 0, sizeof(c));for (int i = 0; i < k; i++){scanf("%d %d", &u, &v);c[u][v] = 1;}int maxs = 0, num = 0;maxs = solve();for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (c[i][j]){c[i][j] = 0;if (solve() < maxs){num++;}c[i][j] = 1;}}}cout << "Board " << ++cases << " have " << num << " important blanks for " << maxs << " chessmen." << endl;}
}int main()
{input();return 0;
}
这篇关于hdu1281 二分图匹配_必要边的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
