首页 > 代码库 > hdu 4619 Warm up 2 (二分匹配）
hdu 4619 Warm up 2 (二分匹配）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4619
题意：
平面上有一些1×2的骨牌，每张骨牌要么水平放置，要么竖直放置，并且保证同方向放置的骨牌不会相互覆盖。水平放置的牌和竖直放置的牌可能相互覆盖，现在要移去一些牌，使得剩下的牌任何两张都不会相互覆盖，问桌面上最多能剩多少张牌。
分析：
如果把每张牌看作一个结点，则共有两类结点，容易联想到二分图。另外，同方向的牌不会相互覆盖，不同方向的可能相互覆盖，易想到二分图的一个重要性质：同类结点间不会连边，不同结点间可以连边。所以显然是这方面的问题了。
解题思路：
根据上述分析，这是一个二分图问题，每张牌作为一个结点，水平放置的成点集X,竖直放置的成点集Y，若两张牌相互覆盖，则两点间连边。这样建图后，一个“覆盖点”对应一条边，成了裸的“最小点覆盖”问题，即：结点数-最大二分匹配数。
代码：
#include <cstdio>#include <cstring>using namespace std;#define N 1200bool mp[N][N];int x[N], y[N], f[N], rm[N], lm[N];int n, m;bool path(int s){ for(int i = 1; i <= m; i++) if(f[i] == 0 && mp[s][i]) { f[i] = 1; if(rm[i] == 0 || path(rm[i])) { rm[i] = s; lm[s] = i; return true; } } return false;}int MaxMatch(){ memset(rm, 0, sizeof(rm)); memset(lm, 0, sizeof(lm)); int ans = 0; for(int i = 1; i <= n; i++) if(!lm[i]) { memset(f, 0, sizeof(f)); if(path(i)) ans++; } return ans;}int main(){ int i, j; while(~scanf("%d %d", &n, &m), n||m) { int a, b; for(i = 1; i <= n; i++) scanf("%d %d", &x[i], &y[i]); memset(mp, false, sizeof(mp)); for(i = 1; i <= m; i++) { scanf("%d %d", &a, &b); for(j = 1; j <= n; j++) if( (a == x[j] && b == y[j]) || (a == x[j] && b == y[j] - 1) || (a == x[j] + 1 && b == y[j]) || (a == x[j] + 1 && b == y[j]-1) ) mp[j][i] = true; } int ans = MaxMatch(); printf("%d\n", n+m-ans); } return 0;}
hdu 4619 Warm up 2 (二分匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。