题目类型 二分匹配, 带花树, 状压dp
题目意思
给出一个 n * m 的字符矩阵 如果字符为 * 表示需要覆盖 每次覆盖可以覆盖一个 1*2 或 2*1的小矩阵 问要把所有 * 都至少覆盖一次需要的次数
解题方法
1.二分匹配
每个 * 字符作为１个点(假设有 x 个点) 然后每个点有一个对称点 即有两个点集 点集 x 由原来的点构成 点集 y 由对称点构成
如果两个点a, b可以一次就覆盖完则 a 与 b的对称点连一条边且 b 与 a的对称点也连一条边
构造出来的二分图的最大匹配假设为 M, 则真正的原点集的最大匹配为 M/2 剩下的独立的点为 x - M个 这些点都需要独立的一次覆盖
那么需要的覆盖次数就是 M/2 + (x - M) 即 x - M/2
2.带花树
用带花树算法解一般图匹配问题 任意图匹配 带花树模版 时间复杂度 O(VE)
3.由于列最多只有10, 可以用状态压缩dp解这道题
dp[i][j] : 完全覆盖前 i 行的星号且 第 i 行状态为 j 的最少需要覆盖次数是多少(j是一个二进制数 当第 k 位为1表示是2*1的小矩阵的上面部分,0表示不是)
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
二分匹配
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char str[50][50];
vector<int>E[500];
bool vis[500];
int y[500];
int n, m, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
bool dfs(int u) {
for( int i=0; i<E[u].size(); i++ ) {
int v = E[u][i];
if(vis[v]) continue;
vis[v] = true;
if(y[v] == -1 || dfs(y[v])) {
y[v] = u;
return true;
}
}
return false;
}
int main() {
freopen("in", "r", stdin);
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for( int i=0; i<n*m; i++ ) E[i].clear();
for( int i=0; i<n; i++ ) scanf("%s", str[i]);
int num = 0;
for( int i=0; i<n; i++ ) {
for( int j=0; j<m; j++ ) {
if(str[i][j] == 'o') continue;
num++;
for( int k=0; k<4; k++ ) {
int tx = i + dx[k];
int ty = j + dy[k];
if(tx >= 0 && tx < n && ty >= 0 && ty < m) {
if(str[tx][ty] == '*') {
E[i*m+j].push_back(tx*m+ty);
}
}
}
}
}
memset(y, -1, sizeof(y));
int ans = 0;
for( int i=0; i<n*m; i++ ) {
memset(vis, 0, sizeof(vis));
if(dfs(i)) ans++;
}
//printf("%d %d\n", num, ans);
printf("%d\n", num-ans/2);
}
return 0;
}
带花树
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 500 + 10;
queue<int>q;
//g[i][j]存放关系图：i,j是否有边,match[i]存放i所匹配的点
bool g[maxn][maxn], inque[maxn], inblossom[maxn];
int match[maxn], pre[maxn], base[maxn];
//找公共祖先
int findancestor(int u, int v) {
bool inpath[maxn] = {false};
while(1) {
u = base[u];
inpath[u] = true;
if(match[u] == -1) break;
u = pre[match[u]];
}
while(1) {
v = base[v];
if(inpath[v]) return v;
v = pre[match[v]];
}
}
//压缩花
void reset(int u, int anc) {
while(u != anc) {
int v = match[u];
inblossom[base[u]] = 1;
inblossom[base[v]] = 1;
v = pre[v];
if(base[v] != anc) pre[v] = match[u];
u = v;
}
}
void contract(int u, int v, int n) {
int anc = findancestor(u, v);
memset(inblossom, 0, sizeof(inblossom));
reset(u, anc); reset(v, anc);
if(base[u] != anc) pre[u] = v;
if(base[v] != anc) pre[v] = u;
for( int i=1; i<=n; i++ ) {
if(inblossom[base[i]]) {
base[i] = anc;
if(!inque[i]) {
q.push(i);
inque[i] = 1;
}
}
}
}
bool dfs(int S, int n) {
for( int i=0; i<=n; i++ ) pre[i] = -1, inque[i] = 0, base[i] = i;
while(!q.empty()) q.pop();
q.push(S); inque[S] = 1;
while(!q.empty()) {
int f = q.front(); q.pop();
for( int i=1; i<=n; i++ ) {
if(g[f][i] && base[i] != base[f] && match[f] != i) {
if(i == S || (match[i] != -1 && pre[match[i]] != -1)) contract(f, i, n);
else if(pre[i] == -1) {
pre[i] = f;
if(match[i] != -1) q.push(match[i]), inque[match[i]] = 1;
else {
f = i;
while(f != -1) {
i = pre[f];
int w = match[i];
match[f] = i;
match[i] = f;
f = w;
}
return true;
}
}
}
}
}
return false;
}
int solve(int n) {
memset(match, -1, sizeof(match));
int ans = 0;
for( int i=1; i<=n; i++ ) {
if(match[i] == -1 && dfs(i, n)) ans++;
}
return ans;
}
char str[50][20];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int main() {
freopen("in", "r", stdin);
int t;
scanf("%d", &t);
while(t--) {
int n, m;
scanf("%d%d", &n, &m);
for( int i=0; i<n; i++ ) scanf("%s", str[i]);
int num = 0;
memset(g, 0, sizeof(g));
for( int i=0; i<n; i++ ) {
for( int j=0; j<m; j++ ) {
if(str[i][j] == 'o') continue;
num++;
for( int k=0; k<4; k++ ) {
int tx = i + dx[k];
int ty = j + dy[k];
if(tx >= 0 && tx < n && ty >= 0 && ty < m) {
if(str[tx][ty] == '*') {
g[i*m+j+1][tx*m+ty+1] = true;
}
}
}
}
}
int ans = solve(n*m);
printf("%d\n", num - ans*2 + ans);
}
return 0;
}
状态压缩dp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int INF = 1<<29;
char str[50][50];
int dp[50][1100];
int n, m;
int ii;
void dfs(int x, int cnt, int rea, int nu) {// x:完成前x位的决策 cnt(二进制数,1表示这一位已覆盖) rea(二进制数,1表示这一位是2*1小矩阵上半部分
if(x == m) { // nu:已经使用了多少次覆盖次数
if(ii == 0) {
if(cnt != ((1<<m)-1)) return ;
dp[ii][rea] = min(dp[ii][rea], 0 + nu);
return ;
}
for( int i=0; i<(1<<m); i++ ) {
int tmp = dp[ii-1][i];
if(tmp == INF) continue;
if(((cnt|i) != ((1<<m)-1) )) continue;
if(dp[ii][rea] < tmp + nu) continue;
dp[ii][rea] = min(dp[ii][rea], tmp + nu);
}
return ;
}
if(str[ii][x] == 'o') dfs(x+1, cnt*2+1, rea*2, nu); //如果是 o 表示已覆盖
else {
if(x<m) dfs(x+1, cnt*2, rea*2, nu); //这一位可以不覆盖
if(x<m) dfs(x+1, cnt*2+1, rea*2+1, nu+1); //可以用一个2*1小矩阵覆盖且这一位是上半部分
if(x<m-1) dfs(x+2, (cnt*2+1)*2+1, rea*4, nu+1); //可以用一个1*2的小矩阵覆盖
}
}
int main() {
freopen("in", "r", stdin);
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for( int i=0; i<n; i++ ) scanf("%s", str[i]);
for( int i=0; i<n; i++ ) {
for( int j=0; j<(1<<m); j++ ) dp[i][j] = INF;
}
for( int i=0; i<n; i++ ) {
ii = i;
dfs(0, 0, 0, 0); // dfs枚举第i行的决策
}
int ans = INF;
for( int i=0; i<(1<<m); i++ ) {
if(dp[n-1][i] != INF) {
ans = min(ans, dp[n-1][i]);
}
}
printf("%d\n", ans);
}
return 0;
}