0%

Leetcode LCP4.覆盖 二分图匹配

Posted on

题面描述 LCP4.覆盖

给你一个最大 $ 8 \times 8 $ 的棋盘，其中有任意多的给定的禁区，求问最多能放进多少 $ 1 \times 2 $ 的多米诺骨牌

首先能想到的肯定是去暴力枚举，即使加上各类剪枝，也非常被卡T掉。
傻傻的我还写了两个版本的暴力(bitset 版本的)，写完就发现除了节省空间以外没有任何时间上的优化

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
class Solution {
5
public:
6
    bool vis[10][10];
7
    int ans,n,m;
8
9
    void dfs(int x,int y,int cur){
10
        if (x==n){
11
            ans=max(ans,cur);
12
            return;
13
        }
14
        if (cur+(m*(n-x-1)+m-y-1)/2<=ans) return;
15
        int nx=x,ny=y+1;
16
        if (ny==m){
17
            ++nx;
18
            ny=0;
19
        }
20
        if (y!=m-1&&!vis[x][y]&&!vis[x][y+1]){
21
            vis[x][y]=vis[x][y+1]=true;
22
            dfs(nx,ny,cur+1);
23
            vis[x][y]=vis[x][y+1]=false;
24
        }
25
        if (x!=n-1&&!vis[x][y]&&!vis[x+1][y]){
26
            vis[x][y]=vis[x+1][y]=true;
27
            dfs(nx,ny,cur+1);
28
            vis[x][y]=vis[x+1][y]=false;
29
        }
30
        dfs(nx,ny,cur);
31
    }
32
33
    int domino(int nn, int mm, vector<vector<int>>& broken) {
34
        n=nn,m=mm;
35
        for (int i=0;i<n;++i){
36
            for (int j=0;j<m;++j){
37
                vis[i][j]=false;
38
            }
39
        }
40
        for (auto i:broken){
41
            vis[i[0]][i[1]]=true;
42
        }
43
        ans=0;
44
        dfs(0,0,0);
45
        return ans;
46
    }
47
};

考虑任意两个相邻的格子，都只能放在同一个多米诺骨牌下。
因此放一个骨牌等价于在棋盘上连一条边。
则此图等价于一个二分图，求最大匹配数。
然后就只剩下建图就做完了。
注意二分图匹配返回的是一共匹配了多少个节点，因此对于此题答案要除以二。

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
template<int maxn>
5
struct MaxMatch{
6
    int n;
7
    vector<int> G[maxn];
8
    int vis[maxn],left[maxn],clk;
9
10
    void init(int n){
11
        this->n=n;
12
        for (int i=0;i<n;++i){
13
            G[i].clear();
14
        }
15
        memset(left,-1,sizeof(left));
16
        memset(vis,-1,sizeof(vis));
17
    }
18
19
    bool dfs(int u){
20
        for (auto&v:G[u]){
21
            if (vis[v]!=clk){
22
                vis[v]=clk;
23
                if (left[v]==-1||dfs(left[v])){
24
                    left[v]=u;
25
                    return true;
26
                }
27
            }
28
        }
29
        return false;
30
    }
31
32
    int match(){
33
        int ret=0;
34
        for (clk=0;clk<n;++clk){
35
            if (dfs(clk)) ++ret;
36
        }
37
        return ret;
38
    }
39
};
40
41
const int d[4][2]={1,0,-1,0,0,1,0,-1};
42
43
class Solution {
44
protected:
45
    int n,m;
46
    bool can[10][10];
47
48
    inline bool can_vis(int x,int y){
49
        if (x<0||x>=n) return false;
50
        if (y<0||y>=m) return false;
51
        return can[x][y];
52
    }
53
54
public:
55
    Solution(){}
56
    int domino(int nn, int mm, vector<vector<int>>& broken) {
57
        int nx,ny;
58
        n=nn,m=mm;
59
        memset(can,true,sizeof(can));
60
        for (auto e:broken){
61
            can[e[0]][e[1]]=false;
62
        }
63
        MaxMatch<70> solver;
64
        solver.init(n*m);
65
        for (int x=0;x<n;++x){
66
            for (int y=0;y<m;++y){
67
                if (!can[x][y]) continue;
68
                for (int i=0;i<4;++i){
69
                    nx=x+d[i][0],ny=y+d[i][1];
70
                    if (!can_vis(nx,ny)) continue;
71
                    solver.G[x*m+y].push_back(nx*m+ny);
72
                }
73
            }
74
        }
75
        return solver.match()/2;
76
    }
77
};