最大独立集：选出最多的点，使选出的点之间没有边

在二分图中：
最大独立集<=> 去掉最少的点，将所有边都破坏掉 <=> 找最小点覆盖 <=> 最大匹配

两个集合总点数为n，最大匹配为m，最大独立集=n-m

思路：
如果两个点可以相互攻击到，则在两个点之间连一条边
转化后的问题等价于：选最多的点，使得点之间没有边
棋盘染色：二分图，隔一个染一个颜色
骑士走到的下一步，必定为与起始位置相反的颜色，因此该棋盘可以看做二分图

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

const int N=110,M=210;

int g[N][N],st[N][N];

typedef pair<int,int> pii;

pii match[N][N];
int n,m,k;

int dx[]={1,2,2,1,-1,-2,-2,-1};
int dy[]={2,1,-1,-2,-2,-1,1,2};

int find(int x,int y)
{
    //遍历(x,y)的邻点
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<1 || a>n || b<1 || b>m) continue;
        if(st[a][b] || g[a][b]) continue;
        st[a][b]=1;
        auto t=match[a][b];
        if(t.x==0 || find(t.x,t.y))
        {
            match[a][b] = {x,y};
            return 1;
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m>>k;
    int kk=k;
    while(k--)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=1;
    }

    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            memset(st,0,sizeof st);
            if((i+j)%2 && g[i][j]==0)
            {
                if(find(i,j)) res++;
            }
        }
    }

    cout<<m*n-res-kk;
    return 0;
}

二刷，最大独立集

两个点不能互相攻击=两个点之间没有边
又练了一遍匈牙利算法

#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int,int> pii;

const int N=110;
int g[N][N],st[N][N];
pii match[N][N];
int n,m,k;

int dx[]={1,2,2,1,-1,-2,-2,-1};
int dy[]={2,1,-1,-2,-2,-1,1,2};

int find(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>n || a<1||b>m||b<1) continue;
        if(g[a][b]||st[a][b]) continue;
        st[a][b]=1;
        auto t=match[a][b];
        if(t.first==0 || find(t.first,t.second))
        {
            match[a][b]={x,y};
            return 1;
        }
    }
    return 0;
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=1;
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            memset(st,0,sizeof st);
            if((i+j)%2 && g[i][j]==0)
            {
                if(find(i,j))
                res++;
            }
        }
    }
    cout<<n*m-res-k<<endl;
    return 0;
}`

三刷，最大独立集=总点数-最小点覆盖=总点数-最大匹配数

这题又用到匈牙利算法，考的是最大独立集
把整个棋盘看出黑白相间的棋盘，由于只能从黑格走到白格，因此满足二分图。
从每个黑格开始，遍历他的邻边，做匈牙利算法

#include <iostream>
#include <cstring>

using namespace std;

const int N=220;
int n,m,k;
int g[N][N],st[N][N];
typedef pair<int,int> pii;

pii match[N][N];
int dx[]={1,2,2,1,-1,-2,-2,-1};
int dy[]={2,1,-1,-2,-2,-1,1,2};


int find(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];

        if(a<1||a>n||b<1||b>m||g[a][b]==1) continue;
        if(!st[a][b])
        {
            st[a][b]=1;
            if(match[a][b].first==0 || find(match[a][b].first,match[a][b].second))
            {
                match[a][b]={x,y};
                return 1;
            }
        }
    }
    return 0;

}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=1;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if((i+j)%2) continue;
            if(g[i][j]==1) continue;
            memset(st,0,sizeof st);
            if(find(i,j)) cnt++;
        }
    }

    cout<<n*m-k-cnt;
    return 0;
}