P3355 骑士共存问题

题目描述

在一个 nn个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入

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

输入输出格式

输入格式：
第一行有 2 个正整数n 和 m (1<=n<=200, 0<=m<n2)，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数，表示障碍的方格坐标。

输出格式：
将计算出的共存骑士数输出

代码

二分图的最大独立集问题，因为黄点只能攻击黄点，而红点只能攻击红点
我们先考虑黑白染色
将 （i+j）&1即黄色染黑，其余点染白。因为我们能相互攻击的点一定是在二分图两侧，然后能攻击的点连边跑最大流就好了

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=400+10,maxm=1000000+100;
int head[maxn*maxn],dis[maxn*maxn],mark[maxn][maxn],vis[maxn*maxn];
int cur[maxn*maxn];
int s,t,n,m,size=1;
int dx[]={1,-1,1,-1,2,2,-2,-2},dy[]={2,2,-2,-2,1,-1,1,-1};
struct edge
{
    int to,next,cap;
}e[maxm];
void addedge(int u,int v,int val)
{
    e[++size].to=v;e[size].cap=val;e[size].next=head[u];head[u]=size;
    e[++size].to=u;e[size].cap=0;e[size].next=head[v];head[v]=size;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int id(int i,int j)
{
    return (i-1)*n+j;
}
bool bfs(int s)
{
    memset(dis,0,sizeof(dis));
    deque<int>q;
    q.push_back(s);
    dis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        for(int i=head[u];i;i=e[i].next)
        {
            int to=e[i].to;
            if(e[i].cap>0&&!dis[to])
            {
                dis[to]=dis[u]+1;
                if(q.empty()||dis[to]>dis[q.front()])q.push_back(to);
                else q.push_front(to);
            }
        }
    }
    return dis[t];
}
int dinic(int u,int f)
{
    if(u==t)return f;
    for(int &i=cur[u];i;i=e[i].next)
    {
        int to=e[i].to;
        if(dis[to]==dis[u]+1&&e[i].cap>0)
        {
            int d=dinic(to,min(f,e[i].cap));
            if(d>0)
            {
                e[i].cap-=d;
                e[i^1].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int maxflow()
{
    int flow=0;
    while(bfs(s))
    {
        memcpy(cur,head,sizeof(head)); 
        while(1)
        {   
        int f=dinic(s,inf);
        if(f==0)break;
        flow+=f;
        }
    }
    return flow;
}
int main()
{
    n=read(),m=read();
    s=0,t=n*n+1;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        mark[x][y]=1;
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        {
          if(mark[i][j])continue;
          int u=id(i,j);
            if(((i+j)&1))
            {
              addedge(s,u,1);
              for(int k=0;k<8;k++)
              {
              int x=i+dx[k],y=j+dy[k];
              if(mark[x][y])continue;
              if(x<1||x>n||y<1||y>n)continue;
              int v=id(x,y);
              addedge(u,v,1);
              }
                
            }
        else addedge(u,t,1);
        }
    printf("%d",n*n-m-maxflow());  
    return 0;
}

P3355 骑士共存问题

原文：https://www.cnblogs.com/DriverBen/p/10576011.html