「Luogu3355」 骑士共存问题

problem

Solution

二分图最大点独立集问题

首先对棋盘黑白染色

从所有无障碍的黑点向能攻击到的无障碍的白点连边

按照二分图最大点独立集=二分图最大匹配，跑二分图匹配即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cmath>
#define maxn 205
#define maxm 40005
using namespace std;
typedef long long ll;

template <typename T>void read(T &t)
{
    t=0;char c=getchar();int f=0;
    while(!isdigit(c)){f|=c=='-';c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

int n,m;
int ocr[maxm];
int ans;

struct edge
{
    int u,v,nxt;
}g[maxm*4];

int head[maxm],ecnt;
void eADD(int u,int v)
{
    g[++ecnt].u=u;
    g[ecnt].v=v;
    g[ecnt].nxt=head[u];
    head[u]=ecnt;
}

inline int trans(int x,int y)
{
    return (x-1)*n+y;
}

int result[maxm],use[maxm],sign;
bool Hungary(int u)
{
    for(register int i=head[u];i;i=g[i].nxt)
    {
        int v=g[i].v;
        if(use[v]==sign)
            continue;
        use[v]=sign;
        if(!result[v] || Hungary(result[v]))
        {
            result[v]=u;
            return true;
        }
    }
    return false;
}

void Calc()
{
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=n;++j)
            if(!ocr[trans(i,j)] && (i+j)&1)
            {
                sign=trans(i,j);
                ans+=Hungary(trans(i,j));
            }
}

const int dx[8]={-2,-2,-1,-1,1,1,2,2},dy[8]={-1,1,-2,2,-2,2,-1,1};
int main()
{
    read(n),read(m);
    for(register int i=1;i<=m;++i)
    {
        int x,y;
        read(x),read(y);
        ocr[trans(x,y)]=1;
    }
    for(register int i=1;i<=n;++i)
        for(register int j=1;j<=n;++j)
            if(!ocr[trans(i,j)] && (i+j)&1)
                for(register int k=0;k<8;++k)
                {
                    int X=i+dx[k],Y=j+dy[k];
                    if(X<1 || X>n || Y<1 || Y>n || ocr[trans(X,Y)])
                        continue;
                    eADD(trans(i,j),trans(X,Y));
                }
    Calc();
    printf("%d",n*n-m-ans);
    return 0;
}