luogu3355 骑士共存问题

像这种蚝神能20分钟A掉的题我就只能想上两节课才搞明白。

话说但凡我能想起做过的另一道题，我也不至于用这么长时间——

这两道题同属网络流的一个套路：棋盘黑白染色求最小割

我们能联想到刚才那道题的话，思路就很明显了。我们先黑白染色，用源点连接所有黑点，流量为1，用汇点连接所有白点，流量为1，然后对于每个黑点，与它能影响到的白点连一条inf。

我们可以这样理解：对于每一次增广，我们增广到的一条路视为一个矛盾。我们可以割掉这条增光路上的黑点或者白点，来解决这个矛盾，这样就是求最小割。对于每个黑点，我们可以看做它有一个矛盾的白点集合S，我们只需要选择其中的一个白点进行解决矛盾的操作，就可以连带着解决这个集合中其它所有矛盾；对于每个白点，也是同理，一旦这个白点被一个黑点解决过，那其它的黑点就不用再考虑解决它。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define big (1000000000 + 10)
#define maxn (500000 + 10)
using namespace std;
int dis[maxn],head[maxn],cur[maxn],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,-2,-1,1,2,-2,-1,1,2};
int cnt,n,m,k,ans,tot,s,t=40001;
bool rb[maxn];
int read(){
    char c;int r=0,f=1;
    c=getchar();
    while (c<'0' || c>'9'){
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9'){
        r=(r*10)+(c^48);
        c=getchar();
    }
    return r*f; 
}
struct edge{
    int next,to,dis;
}ljb[maxn];
void add_edge(int x,int y,int z){
    ljb[++cnt].next=head[x];
    ljb[cnt].to=y;
    ljb[cnt].dis=z;
    head[x]=cnt;
}
void add(int x,int y,int z){
    add_edge(x,y,z);
    add_edge(y,x,0);
}
queue<int> q;
bool bfs(){
    for (int i=s;i<=t;i++) dis[i]=-1;
    q.push(s); dis[s]=0;
    while (!q.empty()){
        int x=q.front(); q.pop();
        for (int i=head[x];i!=-1;i=ljb[i].next){
            int y=ljb[i].to;
            if (dis[y]==-1 && ljb[i].dis>0){
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if (dis[t]!=-1) return 1;
    return 0;
}
int dfs(int x,int low){
    if (x==t) return low;
    for (int& i=cur[x];i!=-1;i=ljb[i].next){
        int y=ljb[i].to;
        if (dis[y]==dis[x]+1 && ljb[i].dis>0){
            int flow=dfs(y,min(low,ljb[i].dis));
            if (flow){
                ljb[i].dis-=flow;
                ljb[i^1].dis+=flow;
                return flow;
            }
        }
    }
    return 0;
}
int main(){
    n=read();m=read();
    for (int i=1;i<=m;i++){
        int x=read(),y=read();
        rb[(x-1)*n+y]=1;
    }
    for (int i=s;i<=t;i++) head[i]=-1;cnt=-1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            int now=(i-1)*n+j;
            if (!rb[now]){
                if (!(i%2^j%2)){
                    add(s,now,1);
                    for (int k=1;k<=8;k++){
                        int x=i+dx[k],y=j+dy[k];
                        if (x>=1 && x<=n && y>=1 && y<=n)
                        { 
                            int z=(x-1)*n+y;
                            if (!rb[z]) add(now,z,big);
                        }
                    }
                }
                else add(now,t,1);
            }
        }
    while (bfs()){
        for (int i=s;i<=t;i++) cur[i]=head[i];
        do{
            tot=dfs(s,big);
            ans+=tot;
        }
        while (tot);
    }
    printf("%d",n*n-m-ans);
}

骑士共存问题解题报告

对棋盘类套路的总结

luogu3355 骑士共存问题