解题报告 P3355 骑士共存问题
题目链接：P3355 骑士共存问题。
题目大意
给定
数据规模：
解法：最大点独立集
经典的二分图最大点独立集模型。
为什么是二分图？
将棋盘黑白染色（好吧国际象棋棋盘本来就是黑白染色的），于是这是个二分图。
为什么是点独立集？
显然一位骑士所能攻击到的位置与该骑士所在位置的颜色不同，所以可以按照这样的关系连边。
怎么建模？
将棋盘黑白染色，钦定棋盘左上角为黑点。
-
有障碍的点直接忽略掉，不参与以下建模过程。
-
源点
s 向所有黑点连边，容量为1 。 -
所有白点向汇点
t 连边，容量为1 。 -
所有黑点向其能攻击到的八个白点连边，容量为无穷大。
跑最大流，答案就是点数减去总点覆盖集的点数，即
注意事项
-
我使用
HLPP 求最大流，时间复杂度O(n^5) 。跑得贼慢。
AC 代码
评测记录。
#include<cstdio>
#include<cstring>
#include<queue>
#include<list>
namespace Qza{
#define MAXN 40005
#define MAXM 400002 //(4*40000+40000)*2 最多 5*4w次加边，每次加边会添加两条边。
#define INF 2147483647
int h[MAXN],f[MAXN],gap[MAXN];
int en[MAXN],to[MAXM],nex[MAXM],w[MAXM];
int bar[202][202],id[202][202];
int dx[4]={-1,-1,-2,-2}; // 上边4个。
int dy[4]={-2, 2, 1,-1}; // 上边4个。
std::list<int> lst[MAXN];
std::vector<std::list<int>::iterator> it;
void add_edge(int x,int y,int v)
{
static int cnt=-1;
nex[++cnt]=en[x]; to[cnt]=y; en[x]=cnt; w[cnt]=v;
nex[++cnt]=en[y]; to[cnt]=x; en[y]=cnt; w[cnt]=0;
}
int bfs(int s,int t)
{
register int u,v,hst;
std::queue<int> q;
for(h[t]=0,q.push(t);!q.empty();) {
u=q.front(); q.pop();
for(int p=en[u];p!=-1;p=nex[p])
if(w[p^1] && !h[v=to[p]] && v!=t)
hst=h[v]=h[u]+1,q.push(v);
}
return hst;
}
int HLPP(int s,int t,int n)
{
if(s==t) return INF;
register int u,v,flow,minhv,nowh=0,hst=bfs(s,t);
if(!h[s]) return 0;
it.resize(n+2);
std::vector<int> buc[MAXN<<1];
h[s]=n;
for(int i=1;i<=n;++i)
if(h[i]) ++gap[h[i]],it[i]=lst[h[i]].insert(lst[h[i]].begin(),i);
else if(i!=t) h[i]=n<<1;
for(int p=en[s];p!=-1;p=nex[p])
if(v=to[p],flow=w[p]) {
f[s]-=flow; f[v]+=flow;
w[p]-=flow; w[p^1]+=flow;
if(f[v]==flow) {
buc[h[v]].push_back(v);
nowh=std::max(nowh,h[v]);
}
}
while(nowh) {
if(buc[nowh].empty()) {--nowh;continue;}
u=buc[nowh].back();
buc[nowh].pop_back();
minhv=n<<1;
for(int p=en[u];f[u]&&p!=-1;p=nex[p])
if(w[p]) {
if(h[v=to[p]]<h[u]) {
flow=std::min(f[u],w[p]);
f[u]-=flow; f[v]+=flow;
w[p]-=flow; w[p^1]+=flow;
if(f[v]==flow) buc[h[v]].push_back(v);
}
else minhv=std::min(minhv,h[v]);
}
if(!f[u]) continue;
if(h[u]<n && !(--gap[h[u]])) {
for(int i=h[u]+1;i<=hst;++i) {
for(std::list<int>::iterator p=lst[i].begin();p!=lst[i].end();++p)
h[*p]=n+1;
gap[i]=0;
lst[i].clear();
}
hst=h[u]-1;
lst[h[u]].clear();
nowh=h[u]=n+1;
buc[nowh].push_back(u);
}
else {
if(h[u]<n) it[u]=lst[h[u]].erase(it[u]);
nowh=h[u]=minhv+1;
if(h[u]<n) {
it[u]=lst[nowh].insert(lst[nowh].begin(),u);
++gap[nowh];
hst=std::max(hst,nowh);
}
buc[nowh].push_back(u);
}
}
return f[t];
}
int read()
{
char ch=getchar(); int x=0;
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=getchar();
return x;
}
#define id(x,y) id[x][y]
#define judge(i,j,t) (1<=(i)+dx[t] && (i)+dx[t]<=n && 1<=(j)+dy[t] && (j)+dy[t]<=n) // 一定要写个 judge ，否则 RE。
#define dir(i,j,t) id(((i)+dx[t]),((j)+dy[t]))
void main()
{
memset(en,0xff,sizeof(en));
int n,m,s,t,maxflow,node;
n=read(); m=read();
s=n*n+1; t=s+1;
for(int i=1,x,y;i<=m;++i) {
x=read(); y=read();
bar[x][y]=1; // barrier。
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(!bar[i][j]) { // 有障碍的点没有 id。
if(id(i,j)=(i-1)*n+j,(i&1)^(j&1)) { // 白点。
add_edge(id(i,j),t,1);
for(int k=0;k<4;++k)
if(judge(i,j,k) && (node=dir(i,j,k))) add_edge(node,id(i,j),INF);
}
else { // 黑点。
add_edge(s,id(i,j),1);
for(int k=0;k<4;++k)
if(judge(i,j,k) && (node=dir(i,j,k))) add_edge(id(i,j),node,INF);
}
}
maxflow=HLPP(s,t,t);
printf("%d",n*n-m-maxflow);
}
}
int main()
{
Qza::main();
return 0;
}