首页 > 代码库 > POJ-3041
POJ-3041
思路:将n个行看作n个点{x_i}(i=1, ..., n),n个列也看作n个点{y_j}(j=1, ..., n)。每个障碍看作一条无向边(x_i, y_j)。则该问题能够归结为求二分图最小点覆盖数,由于最小点覆盖数等于最大匹配数,因此用匈牙利算法求出最大匹配数即可。
算法:
1. 生成两个整数n和m,将网格的规模输入到n,障碍的个数输入到m。
生成一个二维数组g[n][n],两个一维数组match[n]和chk[n]。
g初始化为全0(g[i][j]==1表示i行j列有一个障碍,g[i][j]==0则表示无障碍)。
match初始化为全0(match[j]==i表示y_j的当前匹配到行x_i,match[j]==0时表示未匹配)。
(chk[j]==0表示y_j未被检查,更确切而言是指在这轮步骤中已被匹配,chk[j]==0则表示已被检查)
生成一个整数ans用于保存结果,初始化为0。
2. 依次将m个障碍的所在行列输入到二维数组g。
3. for i from 1 to n do:
1. chk初始化为全0。
2. 对i行执行下述dfs步骤,若dfs步骤返回成功匹配,则将ans加1:
(每次返回成功匹配时,match都会更新,否则不变)
1. for j from 1 to n do:
若第i行j列存在障碍,并且y_j未被检查,则执行下述步骤:
1. 设置y_j已被检查。
2. 若第j列是第一次匹配,则设置match[j]=i并返回成功匹配。
若第j列不是第一次匹配,则执行下述步骤:
1. 生成一个整数t,并设置t=match[j],match[j]=i。
2. 对t行执行dfs步骤,若返回未成功匹配,则将match[j]恢复
为t,否则返回成功匹配。
2. 返回未成功匹配。
4. 输出ans。
#include <iostream>#include <cstring>using namespace std;int n;int g[512][512], match[512], chk[512];int dfs(int i){ for (int j = 1; j <= n; ++j) { if (g[i][j] && !chk[j]) { ++chk[j]; if (!match[j]) { match[j] = i; return 1; } else { int t = match[j]; match[j] = i; if (!dfs(t)) { match[j] = t; } else { return 1; } } } } return 0;}int main(){ int m, ans = 0; cin >> n >> m; while (m--) { int x, y; cin >> x >> y; ++g[x][y]; } for (int i = 1; i <= n; ++i) { memset(chk, 0x00, sizeof(chk)); ans += dfs(i); } cout << ans << endl; return 0;}
POJ-3041