BZOJ 3175: [Tjoi2013]攻击装置( 匈牙利 )

时间：2022-09-19 17:07:13

BZOJ 3175: [Tjoi2013]攻击装置( 匈牙利 )

黑白染成二分图, 然后不能同时选的就连边, 最大匹配数为m, t为不能放的数目, 则题目所求最大点独立集为 n*n-m-t

-------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
const int maxn = 209;
const int dir[8][2] = {{-1, -2}, {-2, -1}, {1, -2},
  {2, -1}, {-1, 2}, {-2, 1}, 
  {1, 2}, {2, 1}};
 
struct edge {
int to;
edge* next;
} E[maxn * maxn * 8], *pt = E, *head[maxn * maxn];
 
void addedge(int u, int v) {
pt->to = v; pt->next = head[u]; head[u] = pt++;
}
 
char str[maxn][maxn];
int N, vis[maxn * maxn], C, match[maxn * maxn], ans;
 
int Id(int x, int y) {
return x * N + y;
}
 
bool dfs(int x) {
for(edge* e = head[x]; e; e = e->next) if(vis[e->to] != C) {
vis[e->to] = C;
if(!~match[e->to] || dfs(match[e->to])) {
match[e->to] = x;
return true;
}
}
return false;
}
 
bool checkY(int x, int y) {
return (x + y) & 1;
}
 
void init() {
scanf("%d", &N);
ans = N * N;
for(int i = 0; i < N; i++) scanf("%s", str[i]);
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) if(str[i][j] == '0') {
int id = Id(i, j);
if(!checkY(i, j)) {
for(int k = 0; k < 8; k++) {
int x = i + dir[k][0], y = j + dir[k][1];
if(x >= 0 && x < N && y >= 0 && y < N && str[x][y] == '0' && checkY(x, y))
addedge(id, Id(x, y));
}
}
} else
ans--;
}
}
 
void work() {
memset(match, -1, sizeof match);
memset(vis, -1, sizeof vis);
int lim = N * N;
for(C = 0; C < lim; C++) if(dfs(C)) ans--;
printf("%d\n", ans);
}
 
int main() {
init();
work();
return 0;
}

-------------------------------------------------------------------------

3175: [Tjoi2013]攻击装置

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 754  Solved: 362
[Submit][Status][Discuss]

Description

给定一个01矩阵，其中你可以在0的位置放置攻击装置。每一个攻击装置（x,y）都可以按照“日”字攻击其周围的 8个位置（x-1,y-2）,(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1), (x+1,y+2),(x+2,y+1)
求在装置互不攻击的情况下，最多可以放置多少个装置。

Input

第一行一个整数N，表示矩阵大小为N*N。接下来N行每一行一个长度N的01串，表示矩阵。

Output

一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。

Sample Input

3
010
000
100

Sample Output

4

HINT

100%数据 N<=200

Source

相关文章