洛谷 P3355 騎士共存問題

題面

題意

給出一張邊長為n,有幾個障礙點的棋盤,問最多可以放幾個騎士使他們不互相攻擊.

做法

我們可以反過來考慮,先将棋盤放滿騎士,計算至少去掉幾個騎士.

經過觀察,我們可以發現,相同顔色的格子上的棋子無法互相攻擊,是以可以讓超級源點連想每一個紅點,每一個黃點連向超級彙點,流量均為一,表示将棋盤放滿,再将紅格子向可以攻擊到的格子連一條邊,流量為INF,如果有流量通過某個點,就說明這個點不放棋子,是以計算這張圖的最小割也就是最大流就能算出至少要拿掉幾個棋子,用總棋子數減掉這個值即可.

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define zh(x,y) ((x-1)*n+y)
#define N 50010
#define INF 0x3f3f3f3f
using namespace std;

int bb=,n,m,first[N],dir[][]= {,,-,,,,-,,-,-,,-,-,-,,-},s,t,ans,deep[N],cur[N];
bool mm[][];
struct Bn
{
    int to,next,quan;
} bn[N*];
queue<int>que;

inline void add(int u,int v,int w)
{
    bb++;
    bn[bb].to=v;
    bn[bb].quan=w;
    bn[bb].next=first[u];
    first[u]=bb;
}

inline void ad(int u,int v,int w)
{
    add(u,v,w);
    add(v,u,);
}

inline bool bfs()
{
    int p,q;
    for(; !que.empty(); que.pop());
    memset(deep,,sizeof(deep));
    que.push(s);
    deep[s]=;
    for(; !que.empty()&&!deep[t];)
    {
        q=que.front();
        que.pop();
        for(p=first[q]; p!=-; p=bn[p].next)
        {
            if(deep[bn[p].to]||!bn[p].quan) continue;
            deep[bn[p].to]=deep[q]+;
            que.push(bn[p].to);
        }
    }
    return deep[t];
}

int dfs(int now,int mn)
{
    if(now==t)
        return mn;
    int res;
    for(int &p=cur[now]; p!=-; p=bn[p].next)
    {
        if(deep[bn[p].to]!=deep[now]+||!bn[p].quan) continue;
        res=dfs(bn[p].to,min(mn,bn[p].quan));
        if(res)
        {
            bn[p].quan-=res;
            bn[p^].quan+=res;
            return res;
        }
    }
    return ;
}

int main()
{
    memset(first,-,sizeof(first));
    int i,j,k,p,q;
//  for(i=0;i<8;i++) cout<<dir[i][0]<<" "<<dir[i][1]<<endl;
    cin>>n>>m;
    t=n*n+;
    for(i=; i<=m; i++)
    {
        scanf("%d%d",&p,&q);
        mm[p][q]=;
    }
    for(i=; i<=n; i++)
    {
        for(j=; j<=n; j++)
        {
            if(mm[i][j]) continue;
            if((i+j)%)
            {
                ad(s,zh(i,j),);
                for(k=; k<; k++)
                {
                    p=i+dir[k][];
                    q=j+dir[k][];
                    if(p<||p>n||q<||q>n||mm[p][q]) continue;
                    ad(zh(i,j),zh(p,q),INF);
                }
            }
            else
            {
                ad(zh(i,j),t,);
            }
        }
    }
    for(; bfs();)
    {
        for(i=s; i<=t; i++) cur[i]=first[i];
        for(q=dfs(s,INF); q; ans+=q,q=dfs(s,INF));
    }
    cout<<n*n-m-ans;
}