【学术篇】网络流24题--骑士共存问题

啥也不说，先上传送门：luogu3355

显然，骑士的步伐有很好的性质：如果我们为棋盘黑白染色，骑士每一步只会从黑格走到白格，或从白格走到黑格。
（这一点下过国际象棋的人都知道，没下过的画一画也知道）

所以我们把棋盘黑白染色，依次标号，然后将障碍格去掉（单独处理）。我们建立源点S和汇点T，从S向所有黑格依次连容量为1的边，从所有白格依次向T连容量为1的边。然后，为避免重复，我们只将每个黑格向骑士能从此格一步走到的白格连容量为正无穷的边，就建立起了一个网络流图。

下图是以题目样例为例，说明一下该如何建图。

图中也添加了很多的说明。。。
所以最后非障碍格中我们不能选的就是网络流图中的最小割。。
那么我们就能够得到下面的式子：

最多放置骑士个数=棋盘上的格子总数-障碍格数-最小割数

代码也就应运而生了..
（我的代码建边方式非常玄学，大家最好不要向我学习。。。）

下面贴代码（码风轻喷..）：

//IDE:DEV-C++ 5.7.1
//代码并没有经过VS加工
#include <cstring>
#include <cstdio>
#include <queue>
using std::queue;

#define gc      getchar()
#define cl(a,b) memset(a,b,sizeof(a))

const int MAXV=0x9C44;
const int MAXE=0x186AF<<2;
const int INF=~0U>>1;

const int kx[8]={-2,-2,-1,-1, 1, 1, 2, 2};
const int ky[8]={-1, 1,-2, 2,-2, 2,-1, 1};

struct edge{
    int to,next,data;
}e[MAXE]; int v[MAXV],tot=1;

int d[MAXV],cur[MAXV];
bool can[202][202];
int s,t;

inline int gnum(){
    int a=0;char c=gc;bool f=0;
    for(;(c<'0'||c>'9')&&c!='-';c=gc);
    if(c=='-') c=gc,f=1;
    for(;c>='0'&&c<='9';c=gc) a=(a<<1)+(a<<3)+c-'0';
    return f?-a:a;
} //读入优化

inline int max(const int &a,const int &b){
    if(a<b) return b; return a; 
}

inline int min(const int &a,const int &b){
    if(a<b) return a; return b;
}

inline void build(int x,int y,int z){
    e[++tot].to=y; e[tot].next=v[x]; e[tot].data=z; v[x]=tot;
    e[++tot].to=x; e[tot].next=v[y]; e[tot].data=0; v[y]=tot;
}

bool bfs(){
    cl(d,-1); d[s]=0;
    for(int i=s;i<=t;i++) cur[i]=v[i];
    queue<int> q; q.push(s);
    while(!q.empty()){
        int x=q.front(); q.pop();
        for(int i=v[x];i;i=e[i].next)
            if(e[i].data&&d[e[i].to]<0){
                d[e[i].to]=d[x]+1;
                q.push(e[i].to);
            }       
    }
    return d[t]>0;
}

int dfs(int x,int mx){
    if(!mx||x==t) return mx;
    int k,s=0;
    for(int i=cur[x];i;i=e[i].next){
        cur[x]=i;
        if(d[e[i].to]==d[x]+1&&(k=dfs(e[i].to,min(mx,e[i].data)))){
            s+=k; mx-=k; e[i].data-=k; e[i^1].data+=k;
            if(!mx) break;
        }
    }
    return s;
}

int dinic(){
    int ans=0;
    while(bfs()) ans+=dfs(s,INF);
    return ans;
}

int main(){
    int n=gnum(),m=gnum(),o=m; s=0,t=n*n+1;
    while(m--) can[gnum()][gnum()]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(can[i][j]) continue;
            if((i+j)&1)
                build((i-1)*n+j,t,1);
            else {
                build(s,(i-1)*n+j,1);
                for(int k=0;k<8;k++){
                    int _i=i+kx[k],_j=j+ky[k];
                    if(_i<1||_i>n||_j<1||_j>n||can[_i][_j]) continue;
                    build((i-1)*n+j,(_i-1)*n+_j,INF);
                }
            }
        }//奇妙的建边..转化公式图上好像有..
    printf("%d",n*n-o-dinic());
} 

反正就是这样。。可能因为我玄学压常跑的还挺快，刷进了第一页。。

The End.