P3355 骑士共存问题题解

题目链接：P3355 骑士共存问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：

棋盘问题考虑黑白染色成为二分图后做。

观察马的性质，可知一个点只能到一个异色点，所以，构造方案可以先将所有同色点放上马，再考虑有那些异色点不可以放置。

方法一：

网络流，时间复杂度为O(|E|min(|E|^0.5,|V|^0.3))

从源点向每个白点连一条限制为1的边（黑色，白色都可以我选定先在白色放满马）（这里的1没有太大的意义，可以理解为每个点一匹马）

从白点向与它不可共存的点，连边，限制为1因为流量最大为1。

从黑点向汇点连一条限制为1的边。

最后答案为n*n-m-ans，表示总点数减去障碍点，再减去冲突的黑点。

#include <bits/stdc++.h>
using namespace std;
const int N=50010; 
const int M=500010;
int tot=1,n,m,s,t,nxt[M],go[M],hd[N],dep[N],cur[N],vis[N],jz[M],ans;
queue<int> q;
bool bfs()
{
       memset(dep,0,sizeof(dep));
       memcpy(cur,hd,sizeof(hd));
       q.push(s);
       dep[s]=1;
       while(!q.empty())
       {
              int u=q.front();
              q.pop();
              for(int i=hd[u];i;i=nxt[i])
               {
                        int v=go[i];
                        if(!jz[i]||dep[v])continue;
                        dep[v]=dep[u]+1;
                        q.push(v);
               }
       }
       return dep[t];
}
int dfs(int u,int flow)
{
       if(u==t)return flow;
       int out=0;
       for(int i=cur[u];i&&flow;i=nxt[i])
       {
                   cur[u]=i;
               int v=go[i];
               if(jz[i]&&dep[v]==dep[u]+1)
               {
                        int res=dfs(v,min(jz[i],flow));
                        if(res)
                        {
                                 jz[i]-=res;jz[i^1]+=res;flow-=res;out+=res;
                        }
               }
       }
       if(out==0) dep[u]=0;
       return out;
}
void add(int u,int v,int w)
{
       nxt[++tot]=hd[u];
       hd[u]=tot;
       go[tot]=v;
       jz[tot]=w;
}
int id(int x,int y)
{
    return (x-1)*n+y;
}
int xj[10]={2,2,-2,-2,1,1,-1,-1};
int yj[10]={1,-1,1,-1,2,-2,2,-2};
int main()
{
       scanf("%d%d",&n,&m);
       s=0,t=n*n+1; 
       for(int i=1;i<=m;i++)
       {
            int x,y;
            scanf("%d%d",&x,&y);
            vis[id(x,y)]=1;
       }
       for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                int ids=id(i,j);
                if(vis[ids])continue;
                if((i+j)%2==0)
                {
                    add(s,ids,1);
                    add(ids,s,0);
                    for(int k=0;k<8;k++)
                    {
                        int x=i+xj[k];
                        int y=j+yj[k];
                        if(x>0&&y>0&&x<=n&&y<=n&&vis[id(x,y)]==0)
                        {
                            add(ids,id(x,y),1e9);
                            add(id(x,y),ids,0);
                        } 
                    }
                }
                else
                {
                    add(ids,t,1);
                    add(t,ids,0);
                }
            }
        while(bfs())
        ans+=dfs(s,1e9);
        printf("%lld\n",n*n-m-ans);
        return 0;
}

方法二：
匈牙利算法。

从白点向限制的黑点连边，跑匈牙利，求最大匹配。

但是加了一个数据，匈牙利跑不过去，所以二分图的问题，最好转成网络流来做，更快。

#include <iostream>
#include <cstdio>
#include <cstring> 
using namespace std;
const int N=50010; 
const int M=500010;
int tot,n,m,nxt[M],go[M],hd[N],girl[N],ans,wz[210][210];
bool bk[N],vis[N];
int xj[10]={2,2,-2,-2,1,1,-1,-1};
int yj[10]={1,-1,1,-1,2,-2,2,-2};
inline int read(){
    int ans=0;char c;bool flag=true;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')flag=false;
    for(;c>='0'&&c<='9';c=getchar())ans=ans*10+c-'0';
    return flag ? ans : -ans;
}
inline void add(int x,int y)
{
    nxt[++tot]=hd[x];go[tot]=y;hd[x]=tot;
    return ;
}
inline bool find(int x)
{
    for(int i=hd[x];i;i=nxt[i])
    {
        int y=go[i];
        if(vis[y])continue;
        vis[y]=1;
        if(!girl[y]||find(girl[y]))
        {
            girl[y]=x;
            return 1;
        }
    }
    return 0;
}
inline int id(int x,int y)
{
    return (x-1)*n+y;
 } 
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=read(),y=read();
        bk[id(x,y)]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            wz[i][j]=id(i,j);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(bk[wz[i][j]])continue;
            if((i+j)%2)
                for(int k=0;k<8;k++)
                {
                    int x=i+xj[k];
                    int y=j+yj[k];
                    if(x>0&&y>0&&x<=n&&y<=n&&bk[wz[x][y]]==0)
                        add(wz[i][j],wz[x][y]);                
                }
            
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((i+j)%2&&!bk[wz[i][j]])
            {
                memset(vis,0,sizeof(vis));
                if(find(wz[i][j]))ans++;
            }        
    printf("%d\n",n*n-m-ans);
    return 0;
}