COGS 746. [网络流24题] 骑士共存
http://www.cogs.pro/cogs/problem/problem.php?pid=746
★★☆ 输入文件：knight.in 输出文件：knight.out 简单对比
时间限制：1 s 内存限制：128 MB
- 骑士共存问题
- «问题描述：
- 在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍，骑士不得进入。
- «编程任务：
- 对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
- 士，使得它们彼此互不攻击。
- «数据输入：
- 由文件knight.in给出输入数据。第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n*n)
- 分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障碍的方格坐标。
- «结果输出:
- 将计算出的共存骑士数输出到文件knight.out。
- 输入文件示例 输出文件示例
- knight.in
- 3 2
- 1 1
3 3
knight.out
- 5
- 最多放置多少个互不攻击的骑士
- 转化为
- 最少拿去几个骑士使剩下的骑士互不攻击
- 最小割
- 根据红黄格构建二分图
- 源点向所有红格连流量为1的边
- 所有黄格向汇点连流量为1的边
- 能互相攻击的格，通一由红格向黄格连流量为1的边
- 障碍格不练边
- 跑最大流
- 最终格子总数-障碍格-最大流
#include<cstdio> #include<queue> using namespace std; int n,m,tot=1,ans; int front[40010],to[4000100],nextt[4000100],cap[4000100]; int dx[8]={-2,-2,-1,1,2,2,1,-1}; int dy[8]={-1,1,2,2,1,-1,-2,-2}; int barrier[201][201]; int lev[40010],cur[40010]; int src,decc; queue<int>q; void add(int u,int v,int w) { to[++tot]=v;nextt[tot]=front[u];front[u]=tot;cap[tot]=w; to[++tot]=u;nextt[tot]=front[v];front[v]=tot;cap[tot]=0; } void insert(int x,int y,int tx,int ty) { add((x-1)*n+y,(tx-1)*n+ty,1); } bool bfs() { for(int i=0;i<=decc;i++) {lev[i]=-1;cur[i]=front[i];} while(!q.empty()) q.pop(); q.push(src);lev[src]=0; while(!q.empty()) { int now=q.front();q.pop(); for(int i=front[now];i;i=nextt[i]) { int t=to[i]; if(cap[i]>0&&lev[t]==-1) { lev[t]=lev[now]+1; q.push(t); if(t==decc) return true; } } } return false; } int dinic(int now,int flow) { if(now==decc) return flow; int rest=0,delta; for(int & i=cur[now];i;i=nextt[i]) { int t=to[i]; if(lev[t]>lev[now]&&cap[i]>0) { delta=dinic(t,min(flow-rest,cap[i])); if(delta) { cap[i]-=delta;cap[i^1]+=delta; rest+=delta;if(rest==flow) break; } } } if(rest!=flow) lev[now]=-1; return rest; } int main() { /*freopen("knight.in","r",stdin); freopen("knight.out","w",stdout);*/ scanf("%d%d",&n,&m); int x,y;decc=n*n+1; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); barrier[x][y]=true; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((i+j)%2) add(src,(i-1)*n+j,1); else add((i-1)*n+j,decc,1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(barrier[i][j]) continue; if((i+j)%2) for(int k=0;k<8;k++) if(i+dx[k]>=1&&i+dx[k]<=n&&j+dy[k]>=1&&j+dy[k]<=n&&!barrier[i+dx[k]][j+dy[k]]) insert(i,j,i+dx[k],j+dy[k]); } ans=n*n-m; while(bfs()) ans-=dinic(src,4000100); printf("%d",ans); }