2 条题解
-
0
#include<bits/stdc++.h> using namespace std; int dx[8]={-2, -1, 1, 2, -2, -1, 1, 2}; int dy[8]={-1, -2, -2, -1, 1, 2, 2, 1}; struct edge{int x, y, pre;}a[210000];int alen, last[11000]; void ins(int x, int y) {a[++alen]={x, y, last[x]}; last[x]=alen;} bool v[110][110]; int n, m, t, match[110000], chw[110000], tsp; bool dfs(int x) { for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(chw[y]!=tsp) { chw[y]=tsp; if(!match[y]||dfs(match[y])) { match[y]=x; return true; } } } return false; } int main() { scanf("%d%d%d", &n, &m, &t); memset(v,0,sizeof(v)); for(int i=1,x,y;i<=t;i++)scanf("%d%d", &x, &y),v[x][y]=1; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!v[i][j]&&(i+j)%2) for(int k=0;k<8;k++) { int x=i+dx[k]; int y=j+dy[k]; if(x>0&&y>0&&x<=n&&y<=m&&!v[x][y])ins((i-1)*m+j, (x-1)*m+y); } int ans=0; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if((i+j)%2&&!v[i][j]) { tsp++; if(dfs((i-1)*m+j)) ans++; } printf("%d", n*m-t-ans); return 0; } -
0
#include<bits/stdc++.h> using namespace std; int dx[8]={-2, -1, 1, 2, -2, -1, 1, 2}; int dy[8]={-1, -2, -2, -1, 1, 2, 2, 1}; struct edge{int x, y, pre;}a[210000];int alen, last[11000]; void ins(int x, int y) {a[++alen]={x, y, last[x]}; last[x]=alen;} bool v[110][110]; int n, m, t, match[110000], chw[110000], tsp; bool dfs(int x) { for(int k=last[x];k;k=a[k].pre) { int y=a[k].y; if(chw[y]!=tsp) { chw[y]=tsp; if(!match[y]||dfs(match[y])) { match[y]=x; return True; } } } return False; } int main() { scanf("%d%d%d", &n, &m, &t); memset(v,0,sizeof(v)); for(int i=1,x,y;i<=t;i++)scanf("%d%d",&x,&y),v[x][y]=1; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!v[i][j]&&(i+j)%2) for(int k=0;k<8;k++) { int x=i+dx[k]; int y=j+dy[k]; if(x>0&&y>0&&x<=n&&y<=m&&!v[x][y])ins((i-1)*m+j, (x-1)*m+y); } int ans=0; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if((i+j)%2&&!v[i][j]) { tsp++; if(dfs((i-1)*m+j)) ans++; } printf("%d", n*m-t-ans); return 0; }
- 1
信息
- ID
- 1467
- 时间
- 2000ms
- 内存
- 64MiB
- 难度
- 8
- 标签
- 递交数
- 164
- 已通过
- 25
- 上传者