首页 > 代码库 > HDU 1281 棋盘游戏 行列匹配
HDU 1281 棋盘游戏 行列匹配
题目来源:HDU 1281 棋盘游戏
题意:有一些点可以放车 放的时候不能相互攻击到 求出哪一些点必须放 不放就不能得到最大的匹配
思路:行列匹配 矩阵的每一个点对于二分图的每一条边 首先求出最大匹配ans 然后如果每次去掉一个点然后再重新求最大匹配 很耗时 可以把第一次二分匹配的图存着
然后那些关键点肯定是是匹配的边 枚举去掉那一个格点(就是去掉一条已经匹配边)如果还能匹配 那么该格点就不是关键点 关键就是不要每次重新再求最大匹配
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int maxn = 110; const int maxm = 10010; bool vis[maxn]; int y[maxn]; int n, m; int a[maxn][maxn]; int b[maxn]; bool dfs(int u) { for(int i = 0; i < m; i++) { int v = i; if(vis[v] || !a[u][i]) continue; vis[v] = true; if(y[v] == -1 || dfs(y[v])) { y[v] = u; return true; } } return false; } int match() { int ans = 0; memset(y, -1, sizeof(y)); for(int i = 0; i < n; i++) { memset(vis, false, sizeof(vis)); if(dfs(i)) ans++; } return ans; } int main() { int cas = 1; int T; int k; //scanf("%d", &T); while(scanf("%d %d %d", &n, &m, &k) != EOF) { memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); while(k--) { int u, v; scanf("%d %d", &u, &v); u--; v--; a[u][v] = 1; } int ans = match(); int sum = 0; for(int i = 0; i < m; i++) { memset(b, 0, sizeof(b)); for(int j = 0; j < m; j++) if(y[j] != -1) b[y[j]] = 1; if(y[i] == -1) continue; int temp = y[i]; y[i] = -1; a[temp][i] = 0; b[temp] = 0; int flag = 0; for(int j = 0; j < n; j++) { memset(vis, 0, sizeof(vis)); if(!b[j] && dfs(j)) flag = 1; if(flag) break; } if(!flag) { sum++; y[i] = temp; } a[temp][i] = 1; } printf("Board %d have %d important blanks for %d chessmen.\n", cas++, sum, ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。