大家都用染色的方式来实现,我用点稍稍不一样的吧:棋盘镜像
将棋盘看成两个棋盘,边只在两个棋盘之间连接,每个棋盘内部没有边。
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] ;
int n,m,t,vis[110][110],v[maxn],tot,head[maxn],match[maxn],
dx[4]={2,2,1,1},dy[4]={1,-1,2,-2} ;
void add(int u,int v) {
edge[++tot].next=head[u]; edge[tot].ver=v; head[u]=tot;
}
bool check(int x,int y) {
if(x>0&&x<=n&&y>0&&y<=m&&!vis[x][y]) return 1;
return 0;
}
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>>m>>t;
for(int i=1;i<=t;i++) {
int x,y;
cin>>x>>y;
vis[x][y]=1;
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(!vis[i][j]) {
int a=(i-1)*m+j;
for(int k=0;k<4;k++) {
int nx=i+dx[k],ny=j+dy[k];
int b=(nx-1)*m+ny;
if(check(nx,ny)) add(a,b),add(b,a) ;//建立无向边,保险一些
}
}
}
}
int ans=0;
for(int i=1;i<=n*m;i++) {
memset(v,0,sizeof(v) );
if(dfs(i)) ans++;
} ans/=2;//由于镜像之后相当于对每个位置的点都进行了匹配,因此要除二
cout<<n*m-ans-t<<endl;
return 0;
}
为什么要建立无向边可以保险一些哈,能不能拓展指点一下?因为考虑是二分图嘛我就只建立了单向边所以没有AC…谢谢!!