当前位置:网站首页>【SSL集训DAY3】控制棋盘【二分图匹配】
【SSL集训DAY3】控制棋盘【二分图匹配】
2022-08-09 22:35:00 【VL——MOESR】
思路:
我们浅推一波可以发现,每个格子看成一个点,向它能走到的点连边,然后就变成了最小覆盖问题
跑个匈牙利不成问题
c o d e code code
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int dx[8] = {
1, 1, 2, 2, -1, -1, -2, -2 };
const int dy[8] = {
2, -2, 1, -1, 2, -2, 1, -1 };
int n, m, btot, wtot;
int a[25][25], color[25][25], link[5010], dian[25][25];
bool v[100010], ma[5010][5010];
bool find(int x) {
for (int i = 1; i <= wtot; i++) {
if (ma[x][i] == 1 && !v[i]) {
v[i] = 1;
int q = link[i];
link[i] = x;
if (q == 0 || find(q))
return 1;
link[i] = q;
}
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
int x, y, p = 0;
while (cin >> x >> y) {
a[x][y] = 1;
p++;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i][j])
continue;
if ((i % 2 == 1 && j % 2 == 1) || (i % 2 == 0 && j % 2 == 0))
color[i][j] = 1, dian[i][j] = ++ btot;
else dian[i][j] = ++ wtot;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!a[i][j]) {
for (int k = 0; k < 8; k++) {
int xx = i + dx[k], yy = j + dy[k];
if (xx < 1 || xx > n || yy < 1 || yy > m || a[xx][yy])
continue;
if (color[i][j] == 1)
ma[dian[i][j]][dian[xx][yy]] = 1;
else
ma[dian[xx][yy]][dian[i][j]] = 1;
}
}
int ans = 0;
for (int i = 1; i <= btot; i++) {
memset(v, 0, sizeof(v));
if(find(i)) ans ++;
}
printf("%d", btot + wtot - ans);
return 0;
}
边栏推荐
猜你喜欢
随机推荐
&& 不是此版本的有效语句分隔符
【集训DAY5】快速排序【模拟】【数学】
LeetCode952三部曲之三:再次优化(122ms -> 96ms,超51% -> 超91%)
十位时间戳转化成时间
函数习题(下)
如何正则匹配乱码?
金仓数据库 KingbaseGIS 使用手册(6.3. 几何对象创建函数)
【JZOF】32从上往下打印二叉树
上海一科技公司刷单被罚22万,揭露网络刷单灰色产业链
力扣:474.一和零
Force Buckle: 474. Ones and zeros
你的手机曾经被监控过吗?
中国SaaS企业排名,龙头企业Top10梳理
Technology feast!Huayun Data brings six topics to OpenInfra Days China
直播间搭建,按钮左滑出现删除等操作按钮
【诗歌】枕上诗书
集群的基础形式
领跑政务云,连续五年中国第一
《GB5084-2021》PDF下载
Gold Warehouse Database KingbaseGIS User Manual (6.2. Management Functions)