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

★★☆ 输入文件：knight.in 输出文件：knight.out 简单对比
时间限制：1 s 内存限制：128 MB

骑士共存问题

«问题描述：

在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘

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

AC日记——[网络流24题]骑士共存 cogs 746-LMLPHP

«编程任务：

对于给定的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

思路：

　　染色；

　　s到黄色连边，流量1；

　　红色到t连边，流量1；

　　然后黄色周围8个点能跳到的点连边，流量INF；

　　上述所有的点都剔除障碍；

来，上代码：

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

struct EdgeType {

    int v,e,f;

};

struct EdgeType edge[*];

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

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

int n,m,s=,t,head[],cnt=,ans,deep[];

char Cget;

bool if_[][];

inline void in(int &now)

{

    now=,Cget=getchar();

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void edge_add(int u,int v,int w)

{

    edge[++cnt].v=v,edge[cnt].f=w,edge[cnt].e=head[u],head[u]=cnt;

    edge[++cnt].v=u,edge[cnt].f=,edge[cnt].e=head[v],head[v]=cnt;

}

bool BFS()

{

    queue<int>que;

    for(int i=s;i<=t;i++) deep[i]=-;

    deep[s]=,que.push(s);

    while(!que.empty())

    {

        int now=que.front();que.pop();

        for(int i=head[now];i;i=edge[i].e)

        {

            if(deep[edge[i].v]<&&edge[i].f)

            {

                deep[edge[i].v]=deep[now]+;

                if(edge[i].v==t) return true;

                que.push(edge[i].v);

            }

        }

    }

    return false;

}

int flowing(int now,int flow)

{

    if(now==t||flow<=) return flow;

    int oldflow=;

    for(int i=head[now];i;i=edge[i].e)

    {

        if(edge[i].f<=||deep[edge[i].v]!=deep[now]+) continue;

        int pos=flowing(edge[i].v,min(flow,edge[i].f));

        flow-=pos;

        oldflow+=pos;

        edge[i].f-=pos;

        edge[i^].f+=pos;

        if(flow==) return oldflow;

    }

    if(oldflow==) deep[now]=-;

    return oldflow;

}

int main()

{

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

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

    in(n),in(m);

    ans=n*n-m;

    t=n*n+;int x,y;

    while(m--)

    {

        in(x),in(y);

        if_[x][y]=true;

    }

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

    {

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

        {

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

            if((i+j)%==)

            {

                edge_add(s,(i-)*n+j,);

                for(int v=;v<=;v++)

                {

                    if(i+dx[v]>&&i+dx[v]<=n&&j+dy[v]>&&j+dy[v]<=n)

                    {

                        if(!if_[i+dx[v]][j+dy[v]])

                        {

                            edge_add((i-)*n+j,(i+dx[v]-)*n+j+dy[v],0x7ffffff);

                        }

                    }

                }

            }

            else edge_add((i-)*n+j,t,);

        }

    }

    while(BFS()) ans-=flowing(s,0x7ffffff);

    cout<<ans;

    return ;

}

Knight

AC日记——[网络流24题]骑士共存 cogs 746

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