Loading...

洛谷P3355 骑士共存问题

check评论:0 条 remove_red_eye浏览量:39 change_historyTags:编程学习笔记
作者 : Decoration date_range日期 : 2019-08-02

原题链接

  • 题目描述

在一个 $n\times n$个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示,棋盘上某些方格设置了障碍,骑士不得进入

对于给定的 $n\times n$ 个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击

  • 题目分析

攻击装置,我们先将点进行黑白染色,然后将不能同时存在的黑点白点进行连边,源点向黑点,流量为$1$,黑点向不能同时存在的白点,流量为$1$,白点向汇点,流量为$1$,然后跑出最大流,输出$n^2-m-maxflow$即可

  • 代码实现
/**************************/
/*It is made by decoration*/
/*gzzkal   gzzkal   gzzkal*/
/*It is made by decoration*/
/**************************/
#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int next,to,flow;
}e[2000010];
int cnt=1,head[400010],dis[400010],vis[400010],n,m,mmp[210][210],c[210][210],cur[400010];
int dx[8]={1,2,2,1,-1,-2,-2,-1},dy[8]={-2,-1,1,2,-2,-1,1,2},s=0,t;
void add(int u,int v,int dis)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].flow=dis;
    head[u]=cnt;
} 
int bfs()
{
    queue<int> q;
    memcpy(cur,head,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(dis,-1,sizeof(dis));
    q.push(s);
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]==-1&&e[i].flow>0)
            {
                dis[v]=dis[u]+1;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dis[t]!=-1;
}
int dfs(int u,int ex)
{
    if(u==t||!ex)
    {
        return ex;
    }
    int flow=0;
    for(int &i=cur[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].flow>0&&dis[v]==dis[u]+1)
        {
            int tmp=dfs(v,min(e[i].flow,ex));
            if(!tmp)
            {
                continue;
            }
            ex-=tmp;
            flow+=tmp;
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            if(!ex)
            {
                break;
            }
        }
    }
    return flow;
}
int main()
{
    cin>>n>>m;
    t=n*n*4+1; 
    int ans=n*n;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        mmp[x][y]=1;
        c[x][y]=(x+y)&1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(mmp[i][j])
            {
                continue;
            }
            if((i+j)&1)
            {
                add(s,((i-1)*n+j),1);
                add((i-1)*n+j,s,0);
                for(int k=0;k<8;k++)
                {
                    int d1=dx[k]+i,d2=dy[k]+j;
                    if(d1>=1&&d2>=1&&d1<=n&&d2<=n)
                    {
                        add((i-1)*n+j,(d1-1)*n+d2,1);
                        add((d1-1)*n+d2,(i-1)*n+j,0);
                    }
                }
            }
            else
            {
                add((i-1)*n+j,t,1);
                add(t,(i-1)*n+j,0);
            }
        }
    }
    while(bfs())
    {
        ans-=dfs(s,0x3f3f3f3f);
    }
    cout<<ans-m;
}

题解 CF993E chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名