COGS746. [网络流24题] 骑士共存

骑士共存问题
«问题描述：
在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘

上某些方格设置了障碍，骑士不得进入。

«编程任务：
对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑
士，使得它们彼此互不攻击。
«数据输入：
由文件knight.in给出输入数据。第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n*n)<n2)，< span="">
分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障
碍的方格坐标。
«结果输出:
将计算出的共存骑士数输出到文件knight.out。
输入文件示例输出文件示例
knight.in
3 2
1 1

3 3

knight.out

二分图最大独立集，转化为二分图最大匹配，从而用最大流解决。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #include<vector>

 using namespace std;

 const int mx[]={,,,-,-,,,-,-};

 const int my[]={,,-,,-,,-,,-};

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}

     return x*f;

 }

 struct edge{int v,nxt,f;}e[mxn<<];

 int hd[mxn],mct=;

 void add_edge(int u,int v,int f){

     e[++mct].v=v;e[mct].f=f;e[mct].nxt=hd[u];hd[u]=mct;return;

 }

 int n,m;

 int S,T;

 int d[mxn];

 int id[][];

 int mp[][];

 bool BFS(int s,int t){

     queue<int>q;

     memset(d,,sizeof d);

     d[s]=;

     q.push(s);

     while(!q.empty()){

         int u=q.front();q.pop();

         for(int i=hd[u];i;i=e[i].nxt){

             int v=e[i].v;

             if(!d[v] && e[i].f){

                 d[v]=d[u]+;

                 q.push(v);

             }

         }

     }

     return d[t];

 }

 int DFS(int u,int lim){

     if(u==T)return lim;

     int tmp,f=;

     for(int i=hd[u];i;i=e[i].nxt){

         int v=e[i].v;

         if(d[v]==d[u]+ && e[i].f){

             tmp=DFS(v,min(lim,e[i].f));

             e[i].f-=tmp;

             e[i^].f+=tmp;

             lim-=tmp;

             f+=tmp;

             if(!lim)return f;

         }

     }

     d[u]=;

     return f;

 }

 inline int Dinic(){

     int res=;

     while(BFS(S,T))res+=DFS(S,1e9);

     return res;

 }

 void solve(){

     int i,j;

     for(i=;i<=n;i++)

      for(j=;j<=n;j++)

          id[i][j]=(i-)*n+j;

     for(i=;i<=n;i++)

      for(j=;j<=n;j++){

          if(mp[i][j])continue;

          if((i+j)%==)//白色

         {

             add_edge(S,id[i][j],);

             add_edge(id[i][j],S,);

              for(int k=;k<=;k++){

                  int nx=i+mx[k],ny=j+my[k];

                  if(nx< || nx>n || ny< || ny>n || mp[nx][ny])continue;

                 add_edge(id[i][j],id[nx][ny],);

                  add_edge(id[nx][ny],id[i][j],);

              }

         }

         else{//黑色

             add_edge(id[i][j],T,);

             add_edge(T,id[i][j],);

         }

      }

     return;

 }

 int main()

 {

     freopen("knight.in","r",stdin);

     freopen("knight.out","w",stdout);

     n=read();m=read();

     int i,j,u,v;

     for(i=;i<=m;i++){

         u=read();v=read();

         mp[u][v]=;//标记障碍

     }

     S=;T=n*n+;

     solve();

     int ans=Dinic();

     ans=n*n-m-ans;

     printf("%d\n",ans);

     return ;

 }

秒客网

COGS746. [网络流24题] 骑士共存

相关文章