AcWing 372. 棋盘覆盖
原题链接
中等
作者:
追着你行走
,
2021-01-13 23:15:27
,
所有人可见
,
阅读 339
来点稍微有点不一样的实现
离散化+全点扫描
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Node{
int ver,next;
}edge[maxn];
map<int,int> mp[110];
int n,t,tot,cnt,head[maxn],v[maxn],match[maxn],vis[110][110] ;
void add(int u,int v) { //建立双向边
edge[++cnt].ver=v; edge[cnt].next=head[u]; head[u]=cnt;
edge[++cnt].ver=u; edge[cnt].next=head[v]; head[v]=cnt;
return ;
}
bool dfs(int x) {
for(int i=head[x],y;i;i=edge[i].next) {
if(!v[y=edge[i].ver]) {
v[y]=1;
if(!match[y]||dfs(match[y]) ) {
match[y]=x; return true;
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>n>>t;
while(t--){
int x,y;
cin>>x>>y;
vis[x][y]=1;
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(vis[i][j]==0) {
if(!mp[i].count(j)) mp[i][j]=++tot; //离散化
if(i-1>0) add(mp[i-1][j],mp[i][j]) ;
if(j-1>0) add(mp[i][j-1],mp[i][j]) ;
}
}
}
int ans=0;
for(int i=1;i<=tot;i++) {
memset(v,0,sizeof(v) ) ;
if(dfs(i)) ans++;
}
cout<<ans/2<<endl;
return 0;
}