/*
最大独立集
选出最多的点 使得选出的点之间没有边
在二分图中 总共n个点
求最大独立集n-m(越大越好)则去掉的点数m越小越好
<=> 去掉最少的点(m个),将所有边都破坏掉
<=> 找最小点覆盖所有m条边
<=> 找最大匹配m
*/
/*
每个不禁止放的点是一个图节点
每两个可以通过日字走到的点之间连一条边
问题为选出最多的点 使得选出来的点之间不能通过日字跳走到
<=>
转化为选出最多的点 使得选出来的点之间没有边
求最大匹配用得在二分图情况下才能用匈牙利
那么我们类似372把row+col = 奇or偶 分为 白or黑节点
o . o . o
. o . o .
o . o . o
. o . o .
o . o . o
可以发现白节点通过日字跳只能走到黑节点--这是一个二分图
即可以用匈牙利算法做
匈牙利算法求出得最大匹配数 = n*m - res(最多可以剩余不冲突的点数)
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m,k;
PII match[N][N];
bool g[N][N],st[N][N];
int dirs[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
bool find(int x,int y)
{
for(int i = 0;i<8;i++)
{
int nx = x+dirs[i][0],ny = y+dirs[i][1];
if(nx<1 || nx>n || ny<1 || ny>m || g[nx][ny] || st[nx][ny]) continue;
st[nx][ny] = true;//男[x,y] 找到女[nx,ny]
PII t = match[nx][ny];//t为女[nx,ny]现在匹配的对象
if(t.x==0||find(t.x,t.y))//如果女[nx,ny]没有匹配对象或者现配t可以去找其他妹子 那就把[nx,ny]给[x,y]
{
match[nx][ny] = {x,y};
return true;
}
}
return false;
}
int main()
{
cin >> n >> m >> k;
for(int i = 0;i<k;i++)
{
int x,y;
cin >> x >> y;
g[x][y] = true;
}
int res =0;
for(int i =1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
if(g[i][j] || (i+j)%2)continue;
memset(st,0,sizeof st);
if(find(i,j))res++;
}
}
cout << n*m - k - res << endl;
return 0;
}
棒(๑•̀ㅂ•́)و✧
tql
为什么要(i+j)%2???
奇点,偶点