题解:
二分图匹配
看看是否能达到目标
代码:
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=200005; int num,ne[N],fi[N],zz[N],k,cnt,a[40][40],f[N],match[N],x,y,n,m; void jb(int x,int y) { ne[++num]=fi[x]; fi[x]=num; zz[num]=y; ne[++num]=fi[y]; fi[y]=num; zz[num]=x; } int dfs(int x) { for (int i=fi[x];i;i=ne[i]) if (!f[zz[i]]) { f[zz[i]]=1; if (!match[zz[i]]||dfs(match[zz[i]])) { match[zz[i]]=x; return 1; } } return 0; } int main() { while (~scanf("%d%d%d",&m,&n,&k)) { memset(fi,0,sizeof fi); memset(a,0,sizeof a); memset(match,0,sizeof match); num=cnt=0; for (int i=1;i<=k;i++) { scanf("%d%d",&x,&y); a[y][x]=-1; } if ((n*m-k)%2) { puts("NO"); continue; } for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) if (!a[i][j])a[i][j]=++cnt; for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) if (a[i][j]!=-1) { if (a[i+1][j]!=-1&&i!=m)jb(a[i][j],a[i+1][j]); if (a[i][j+1]!=-1&&j!=n)jb(a[i][j],a[i][j+1]); } int ans=0; for (int i=1;i<=cnt;i++) { memset(f,0,sizeof f); ans+=dfs(i); } ans/=2; if (ans*2==cnt)puts("YES"); else puts("NO"); } }