题目大意:给定棋盘,棋盘上有若干个被删除的点,现在有1*2多米诺骨牌,求至少多少张将棋盘全覆盖(可越界可重叠)
(这题是这题的升级版
思路:二分图匹配
对于多米诺骨牌来说,它有两个点。我们将一张骨牌拆成两个点,再将棋盘黑白染色,不难发现,两个点的颜色一定不同,至此可以建图了,一个棋盘可以这样染色
10101
01010
10101
然后分黑白两个集合,假设我把黑点作为左集合,那么那个黑点周围存在的白点就是黑点要连的边,跑一遍二分图匹配,我们可以求出不重叠的情况下尽量覆盖多的点的最小边数,最后还剩一些孤立的点,需要单独对它覆盖,这些点的数量 = =存在的总点数 - 最大边数*2,所以ans = 存在的总点数 - 最大边数
(这题比较巧妙的还是转化成二分图这一步)
#include <cmath> #include <cstring> #include <algorithm> #include <map> #include <list> #include <queue> #include <vector> #include <iostream> #include <cstdio> #include <cstdlib> using namespace std; typedef long long ll; #define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++) #define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--) #define scd(v) scanf("%d",&v) #define scdd(a,b) scanf("%d %d",&a,&b) #define endl "\n" #define IOS ios::sync_with_stdio(false) #define pb push_back #define all(v) v.begin(),v.end() //#define int long long #define odd(x) x&1 #define mst(v,a) memset(v,a,sizeof(v)) #define lson p<<1 ,l,mid #define rson p<<1|1,mid+1,r #define ls p<<1 #define rs p<<1|1 #define fi first #define se second #define pii pair<int,int> #define pdd pair<double,double> const int N=400+10; int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}}; int n,m; char mp[N][N]; int v[N*N]; int link[N*N]; vector <int > G[N*N]; int tot;//坐标的编号 bool dfs(int x) { for(int i=0 ;i<G[x].size() ;i++) { int y = G[x][i]; if( v[y]) continue; v[y]=1; if( !link[y] || dfs(link[y]) ) { link[y]=x; return true; } } return false; } void solve() { //二分图染色建图 int num=0;//总点数 _for(i,1,n) { _for(j,1,m) { if( mp[i][j]=='*' ) num++; if( (i+j)%2==0 && mp[i][j]!='o' )//黑 { int id = (i-1)*m+j; ++tot;//黑点 for(int k=0 ;k<4 ;k++) { int xx = i+dir[k][0]; int yy = j+dir[k][1]; if( 1<=xx && xx<=n && 1<=yy && yy<=m && mp[xx][yy]!='o') { int idd = (xx-1)*m+yy; G[tot].pb(idd); } } } } } int ans=0; _for(i,1,tot) { mst(v,0); if( dfs(i) ) ans++; } cout<<num-ans<<endl; } signed main() { //!! // freopen("data.txt","r",stdin); //!! IOS; int T;cin>>T; while(T--) { mst(G,0);mst(link,0); tot=0; cin>>n>>m; _for(i,1,n) _for(j,1,m) cin>>mp[i][j]; solve(); } }