题解 P3355 【骑士共存问题】

# 很明显的最大流最小割定理 思路和方格取数问题类似： ### 1.黑白染色 ### 2.按照约束关系建图，求最小割（最好使用效率高一点的最大流算法如：[Dinic+当前弧优化](https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-jiang-xie-zhi-dinic)/[isap/hlpp](https://www.luogu.org/blog/ONE-PIECE/jiu-ji-di-zui-tai-liu-suan-fa-isap-yu-hlpp)） ### 3.答案就是n*n-m-maxflow ------------ 解释一下： 第一步~~**黑白染色是看见网格图就该想到的常规思路**~~，什么叫黑白染色：我们把图按照点的横纵坐标之和的奇偶性可以划分为黑格和白格，黑格连汇点，白格连源点。 ### 什么时候该用黑白染色？ 当不同奇偶性的点会相互影响而同奇偶性的点不会相互影响时就用黑白染色，如本题中在奇数点放骑士只会导致一些偶数点不能放骑士，而不会影响奇数点。 第二步建图： 按照约束关系，把给每个白格向会影响的黑格加一条边（因为刚才是白格连源点，所以要从白格向黑格加边） 求最大流（即最小割） 第三步：n*n-m是可以放置的总格子数，maxflow是最小割（至少要拿掉多少个骑士才能满足题意） ------------ ## 代码：（我用的是Dinic加当前弧优化） ``` #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int inf=1<<30; inline int Read(){ int x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*f; } int n,m; int top=1; int head[41011]; int s,t; struct Node{ int v; int val; int next; }node[720020];//每个点向源点或汇点连一条边，最多向周围8个点连边，所以最多200*200*(8+1)*2（反向边）=720000条边 inline void addedge(int u,int v,int val){ node[++top].v=v; node[top].val=val; node[top].next=head[u]; head[u]=top; } inline void add(int u,int v,int val){ addedge(u,v,val); addedge(v,u,0); } int dep[41010]; int cur[41010];//当前弧 bool bfs(){ register int i; for(i=1;i<=t;i++)cur[i]=head[i],dep[i]=-1; dep[s]=0; queue<int>q; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(i=head[u];i;i=node[i].next){ int d=node[i].v; if(dep[d]==-1&&node[i].val){ dep[d]=dep[u]+1; q.push(d); } } } return dep[t]!=-1; } int maxflow=0; int dfs(int u,int flow){ if(u==t){ maxflow+=flow; return flow; } int used=0; for(int i=cur[u];i;i=node[i].next){ cur[u]=i; int d=node[i].v; if(node[i].val&&dep[d]==dep[u]+1){ int mi=dfs(d,min(flow-used,node[i].val)); if(mi){ node[i].val-=mi; node[i^1].val+=mi; used+=mi; if(used==flow)break; } } } return used; } int Dinic(){ maxflow=0; while(bfs())dfs(s,inf); return maxflow; }//求最小割 int map[201][201]; int fx[8]={-2,-2,-1,-1,1,1,2,2}; int fy[8]={1,-1,2,-2,2,-2,1,-1}; int main(){ int i,j,k; n=Read(),m=Read(); int x,y; s=n*n+1,t=n*n+2; for(i=1;i<=m;i++)x=Read(),y=Read(),map[x][y]=1; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(map[i][j])continue; int now=(i-1)*n+j; if((i+j)&1){ add(s,now,1); for(k=0;k<=7;k++){ int dx=i+fx[k],dy=j+fy[k]; if(dx<1||dy<1||dx>n||dy>n||map[dx][dy])continue; add(now,(dx-1)*n+dy,1); } } else add(now,t,1); } } printf("%d",n*n-m-Dinic());//能放的总数-最小割 return 0; } ``` ~~[水双倍经验](https://www.luogu.org/problemnew/show/P4304)~~