首页 > 代码库 > HDU 1281 棋盘游戏(二分匹配 与 删边)
HDU 1281 棋盘游戏(二分匹配 与 删边)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1281
根据题目描述,什么是重要点?在求出最大匹配后,进行枚举,依次删边,看最大匹配数会不会发生改变,改变的话,那么该点就是重要点。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <math.h> #define init(a) memset(a,0,sizeof(a)) #define PI acos(-1,0) using namespace std; const int maxn = 110; const int maxm = 10100; #define lson left, m, id<<1 #define rson m+1, right, id<<1|1 #define min(a,b) (a>b)?b:a #define max(a,b) (a>b)?a:b int mar[maxn][maxn]; int G[maxn][maxn]; int line[maxn]; bool vis[maxn]; int n,m,k; int DFS(int u) { for(int v = 1;v<=m;v++) { if(G[u][v] && !vis[v]) { vis[v] = 1; if(line[v] == -1 || DFS(line[v])) { line[v] = u; return 1; } } } return 0; } int K_M() { int ans = 0; memset(line,-1,sizeof(line)); for(int i = 1;i<=n;i++) { init(vis); ans += DFS(i); } return ans; } int main() { int x[maxm],y[maxm],C = 0; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { C++; init(G); for(int i = 1;i<=k;i++) { scanf("%d%d",&x[i],&y[i]); G[x[i]][y[i]] = 1; } int ans = K_M(); int num = 0; for(int i = 1;i<=k;i++) { G[x[i]][y[i]] = 0;//删边 if(ans > K_M()) num++; G[x[i]][y[i]] = 1;//恢复 } printf("Board %d have %d important blanks for %d chessmen.\n",C,num,ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。