关键词：
题意：
在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘
上某些方格设置了障碍，骑士不得进入。
对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。
n<=200,m<=n^2
思路：经典的二分图最大独立集，采用黑白点染色的思想。
如果按照相邻点黑白不同染色，可以发现每次跳到的点必定与现在所在点不同色，二分图最大匹配即可。
每切断一条黑白点之间的边就是少放了一个骑士，用最小割算出最少要切断几条边，总数减去有障碍的再减切断的边数就是最大匹配数，最大独立集又可以转化为最大匹配数。
这里用最小割来解决，因为不能允许任何黑白点之间的任何一条边有流量，符合最小割的思想。
1 const dx:array[1..8]of longint=(-2,-2,-1,-1,1,1,2,2); 2 dy:array[1..8]of longint=(-1,1,-2,2,-2,2,-1,1); 3 var head,vet,next,len,fan,gap,dis:array[0..500000]of longint; 4 b,num,a:array[1..300,1..300]of longint; 5 n,m,i,tot,x,y,k,j,source,src,s:longint; 6 7 procedure add(a,b,c:longint); 8 begin 9 inc(tot); 10 next[tot]:=head[a]; 11 vet[tot]:=b; 12 len[tot]:=c; 13 head[a]:=tot; 14 end; 15 16 function min(x,y:longint):longint; 17 begin 18 if x<y then exit(x); 19 exit(y); 20 end; 21 22 function dfs(u,aug:longint):longint; 23 var e,v,val,flow,t:longint; 24 begin 25 if u=src then exit(aug); 26 flow:=0; val:=s-1; 27 e:=head[u]; 28 while e<>0 do 29 begin 30 v:=vet[e]; 31 if len[e]>0 then 32 begin 33 if dis[u]=dis[v]+1 then 34 begin 35 t:=dfs(v,min(len[e],aug-flow)); 36 len[e]:=len[e]-t; 37 len[fan[e]]:=len[fan[e]]+t; 38 flow:=flow+t; 39 if dis[source]>=s then exit(flow); 40 if aug=flow then break; 41 end; 42 val:=min(val,dis[v]); 43 end; 44 e:=next[e]; 45 end; 46 if flow=0 then 47 begin 48 dec(gap[dis[u]]); 49 if gap[dis[u]]=0 then dis[source]:=s; 50 dis[u]:=val+1; 51 inc(gap[dis[u]]); 52 end; 53 exit(flow); 54 end; 55 56 function maxflow:longint; 57 var ans:longint; 58 begin 59 fillchar(gap,sizeof(gap),0); 60 fillchar(dis,sizeof(dis),0); 61 gap[0]:=s; ans:=0; 62 while dis[source]<s do ans:=ans+dfs(source,maxlongint); 63 exit(ans); 64 end; 65 66 begin 67 assign(input,'codevs1922.in'); reset(input); 68 assign(output,'codevs1922.out'); rewrite(output); 69 read(n,m); 70 for i:=1 to n do 71 for j:=1 to n do 72 begin 73 inc(s); a[i,j]:=(i+j+1) mod 2; num[i,j]:=s; 74 end; 75 for i:=1 to m do 76 begin 77 read(x,y); 78 b[x,y]:=1; 79 end; 80 s:=n*n+2; 81 for i:=1 to n do 82 for j:=1 to n do 83 if (a[i,j]=1)and(b[i,j]=0) then 84 begin 85 for k:=1 to 8 do 86 begin 87 x:=i+dx[k]; y:=j+dy[k]; 88 if (x>0)and(x<=n)and(y>0)and(y<=n)and(b[x,y]=0) then 89 begin 90 fan[tot+2]:=tot+1; 91 fan[tot+1]:=tot+2; 92 add(num[i,j],num[x,y],1); 93 add(num[x,y],num[i,j],0); 94 end; 95 end; 96 end; 97 source:=50000; src:=50001; 98 for i:=1 to n do 99 for j:=1 to n do 100 if a[i,j]=1 then 101 begin 102 fan[tot+2]:=tot+1; 103 fan[tot+1]:=tot+2; 104 add(source,num[i,j],1); 105 add(num[i,j],source,0); 106 end 107 else if b[i,j]=0 then 108 begin 109 fan[tot+2]:=tot+1; 110 fan[tot+1]:=tot+2; 111 add(num[i,j],src,1); 112 add(src,num[i,j],0); 113 end; 114 writeln(n*n-m-maxflow); 115 close(input); 116 close(output); 117 end.
codevs1922骑士共存问题——网络流
...割，最小割的意义就是看至少要放弃几个点（即这里不放骑士）才能使他们不会互相攻击，最后用总格数减去最小割时记得也要减去障碍数，即n*n-ans-m.具体细节看代码：#include<cstdio>#include<cstring&g 查看详情
「codves1922」骑士共存问题（二分图的最大独立集|网络流）&dinic
首先是题目链接 http://codevs.cn/problem/1922/结果发现题目没图（心情复杂然后去网上扒了一张图大概就是这样了。如果把每个点和它可以攻击的点连一条边，那问题就变成了求二分图的最大独立集了（二分图最大独立集：即一个... 查看详情
骑士共存问题(代码片段)
...心，细心观察他能得到一个很重要的规律：黄色格子上的骑士只能攻击红色格子上的骑士，反之同理。因此，我们可以把棋盘进行黑白染色，然后白点放在图的左侧，黑点在图的右侧，有点像二分图的感觉。接下来切入正题了：... 查看详情
洛谷p3355骑士共存问题最小割
同方格取数问题：https://www.cnblogs.com/lokiii/p/8430720.html记得把障碍点去掉，不连边也不计入sum#include<iostream>#include<cstdio>#include<queue>#include<cstring>usingnamespacestd;constintN=100005,inf 查看详情
网络流24题-题目总结
...大流23火星探险问题线性规划网络优化最小费用最大流24骑士共存问题二分图最大独立集网络最小割 查看详情
网络流24题骑士共存问题（最大流）
【codevs1922】骑士共存问题题目描述 Description在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算... 查看详情
[网络流24题]骑士共存问题(代码片段)
神仙建图...最多可以放上几个，也就是全都放上去之后尽量少删掉几个。发现马总是会由同色攻击至异色，于是将两点之间连边，最后一定是一个二分图。最后删掉的就是二分图的最小割，也就是最大匹配。然后随便固定一个顺... 查看详情
骑士共存问题(二分图最大独立集)
//http://www.cnblogs.com/IMGavin/#include<iostream>#include<stdio.h>#include<cstdlib>#include<cstring>#include<queue>#include<vector>#include<map>#include< 查看详情
网络流24题骑士共存问题（最大流）
【网络流24题】骑士共存问题（最大流）题面Cogs题解这题本质上和方格取数问题没有任何区别首先也是可以黑白染色因为马必定会跳到异色点上面去然后同样的，源点向一种颜色，另一种颜色向汇点连边因为代价就是1，所以容... 查看详情
p3355骑士共存问题最小点覆盖网络流24题(代码片段)
思路 显然棋盘上的每个点有三种形态：障碍物，马，已存的马能跳到的不能放马的点 显然1、3在处理时可以归为一类，则共有两种点态。 所以这题可以看成一个二分图来做 每个马最多能覆盖棋盘上... 查看详情
[luogup3355]骑士共存问题（二分图最大独立集）
...向T连接一条容量为1的有向边。从每个可用的黑色格子向骑士一步能攻击到的可用的白色格子连接一条容量为无穷大的有向边。求出 查看详情
[网络流24题]骑士共存问题
题面：传送门思路：基本上和方格取数问题差不多这道题可以证明，如果把每两个不能共存的点连在一起，那么这个图没有奇环，是一个二分图同时，如果把这个图像国际象棋一样黑白染色，那么连边的两个点颜色不同源点连黑... 查看详情
[网络流24题]骑士共存问题(代码片段)
题目链接：戳我互不侵犯？？？这么多种走位的方式，当然没有办法动态规划啦！（反正我不会网络流可是解决规划问题的大利器啊！有木有想到二分图最大点权独立集呢！黑白染色+向可以走到的地方连边+跳过障碍物点——求... 查看详情
p3355骑士共存问题(代码片段)
二分图最大独立集先给出二分图最大独立集的概念：选择最多的点，使任何边的两边不被同时选中。并且有结论：最大独立集=节点总数-最大匹配。这道题为什么是二分图？我们可以通过((x,y))中的(x+y)的奇偶性来构造二分图，显... 查看详情
洛谷[p3355]骑士共存问题
二分图求最大独立点集本问题在二分图中已处理过,此处用dinic写了一遍#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<queue>#include<cstring>usingnamespacestd;constintM 查看详情
[网络流24题]骑士共存问题(代码片段)
...分图最大点独立集问题。要求在棋盘上放最多互不攻击的骑士，即在棋盘中拿走最少的骑士，使得剩下的骑士互不攻击。黄格只能攻击红格，红格也只能攻击黄格，所以考虑建立二分图。源点向所有红格连流量为1的边，所有黄... 查看详情
网络流24题洛谷3355骑士共存(代码片段)
转换成最小割；#include<bits/stdc++.h>usingnamespacestd;constintmx[9]=2,2,-2,-2,-1,1,-1,1;constintmy[9]=-1,1,-1,1,2,2,-2,-2;constintN=100000+10,inf=1e8+7;queue<int>q;inthh[N<<2],head[N&l 查看详情
p3355骑士共存问题二分建图+当前弧优化dinic(代码片段)
P3355骑士共存问题题意： 也是一个棋盘，规则是“马”不能相互打到。思路： 奇偶点分开，二分图建图，这道题要注意每个点可以跑八个方向，两边都可以跑，所以边=20*n*n。 然后dinic要用当前弧优化。#include<... 查看详情