这个码量绝对是业界大毒瘤......
300行，6.5k，烦的要死......
题意：给你一个网格图，里面有0或1。你需要把一些0换成1使得存在某两个0不四联通。输出最小的换的数量。无解-1。
n,m<=1e9,网格中1的数量<=1e5,多组数据。
首先我们发现，最多只要2就行了(围住一个角落)，所以答案是[-1,2]中的整数。
然后考虑何时为-1：0的数目小于2或等于2且相连。
何时为0：图初始就不连通。
何时为1：图中存在割点。
除此之外就是2了。
然后发现图很大，c很小，考虑离散化。
然后发现我们只要把每个1周围的点提取出来即可。
提取3×3是错误的，有个众人皆知的样例：
0 0 0
0 0 0
0 1
显然提取之后会有一个割点在原图正中间，但是实际上它并不是割点。
然后我们暴力一点，提取5×5即可......
算法流程：提取点，编号。然后判断联通性。然后做tarjan，判断割点。
然后又有好多坑点...比如割点必须在某个1的周围3×3区域(易证)，如果忽视这个就会出现一种毒瘤情况：
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
可以发现在奇怪的地方出现了割点...
然后还要特判，(n - 1)(m - 1) = 0的时候答案不可能为2。
然后怒写一天半终于对了，又发现map太慢跑不过......手写hash。
终于A了....然后uoj日常97分......
[update]如何判断答案为0：对那些提取出来的非关键点进行并查集。然后枚举每个关键点连通块，如果某个关键点连通块连着两个并查集，答案为0。
#include <cstdio>
#include <algorithm>
#include <cstring> inline void read(int &x) {
x = ;
char c = getchar();
while(c < '' || c > '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} const int N = ;
const int dx[] = {, , , -};
const int dy[] = {, , -, }; const int MO = , B = ;
struct POS {
int x, y, h;
POS(int xx = , int yy = ) {
x = xx;
y = yy;
h = (1ll * x * B + y) % MO;
if(h < ) {
h += MO;
}
}
inline bool operator ==(const POS &d) const {
return x == d.x && y == d.y;
}
};
struct Node {
int nex, val;
POS p;
}node[N * ]; int top;
struct MAP {
int e[MO];
inline void insert(const POS &d, const int &a) {
node[++top].val = a;
node[top].nex = e[d.h];
node[top].p = d;
e[d.h] = top;
return;
}
inline int find(const POS &d) { // if not exist return 0
for(int i = e[d.h]; i; i = node[i].nex) {
if(node[i].p == d) {
return node[i].val;
}
}
return ;
}
inline void clear() {
memset(e, , sizeof(e));
return;
}
}mp, use; int n, m, c, xi[N], yi[N], tot, num, root;
int dfn[N * ], low[N * ], vis[N * ];
bool cut[N * ], vis_c[N], OK; inline void np(int x, int y) {
if(!mp.find(POS(x, y)) && !use.find(POS(x, y))) {
mp.insert(POS(x, y), ++tot);
}
return;
} inline int get(int x, int y) {
return mp.find(POS(x, y));
} void tarjan(int s, int x, int y) {
dfn[s] = low[s] = ++num;
int temp = ;
for(int i = ; i < ; i++) {
int t = get(x + dx[i], y + dy[i]);
if(!t) {
continue;
}
if(!dfn[t]) {
tarjan(t, x + dx[i], y + dy[i]);
low[s] = std::min(low[s], low[t]);
if(low[t] >= dfn[s]) {
temp++;
}
}
else {
low[s] = std::min(low[s], dfn[t]);
}
}
if(temp >= || (temp == && s != root)) {
cut[s] = ;
}
return;
} void DFS_1(int s, int x, int y, int temp) {
vis[s] = temp;
for(int i = ;i < ; i++) {
int t = get(x + dx[i], y + dy[i]);
if(!t) {
continue;
}
if(!vis[t]) {
DFS_1(t, x + dx[i], y + dy[i], temp);
}
}
return;
} bool fd;
int number; bool DFS_2(int s, int x, int y) {
vis_c[s] = ;
for(int i = ; i < ; i++) {
if(use.find(POS(x + dx[i], y + dy[i]))) {
int ed = use.find(POS(x + dx[i], y + dy[i]));
if(vis_c[ed]) {
continue;
}
int t = DFS_2(ed, x + dx[i], y + dy[i]);
if(!t) {
return ;
}
}
else if(get(x + dx[i], y + dy[i])) {
if(!fd) {
number = vis[get(x + dx[i], y + dy[i])];
fd = ;
}
else if(number != vis[get(x + dx[i], y + dy[i])]) {
OK = ;
return ;
}
}
}
return ;
} inline bool check() {
OK = ;
int temp = ;
for(int i = ; i <= c; i++) {
for(int x = xi[i] - ; x <= xi[i] + ; x++) {
for(int y = yi[i] - ; y <= yi[i] + ; y++) {
if(vis_c[i]) {
continue;
}
if(mp.find(POS(x, y)) && !vis[get(x, y)]) {
++temp;
DFS_1(get(x, y), x, y, temp);
goto f1;
}
}
}
f1:
if(!vis_c[i]) {
fd = ;
DFS_2(i, xi[i], yi[i]);
}
if(!OK) {
break;
}
}
return !OK;
} inline int solve() {
read(n);
read(m);
read(c);
if(!c) {
if(n == && m == ) {
return -;
}
if(n == || m == ) {
if(n == || m == ) {
return -;
}
return ;
}
return ;
}
for(int i = ; i <= c; i++) {
read(xi[i]);
read(yi[i]);
use.insert(POS(xi[i], yi[i]), i);
}
if(c + >= 1ll * n * m) {
return -;
}
for(int i = ; i <= c; i++) {
for(int x = xi[i] - ; x <= xi[i] + ; x++) {
for(int y = yi[i] - ; y <= yi[i] + ; y++) {
if(x > && y > && x <= n && y <= m && (x != xi[i] || y != yi[i])) {
np(x, y);
}
}
}
}
if(check()) {
return ;
}
if(c + == 1ll * n * m) {
return -;
}
if(m == || n == ) {
return ;
}
for(int i = ; i <= c; i++) {
for(int x = xi[i] - ; x <= xi[i] + ; x++) {
for(int y = yi[i] - ; y <= yi[i] + ; y++) {
if(!use.find(POS(x, y))) {
root = get(x, y);
if(dfn[root]) {
continue;
}
tarjan(root, x, y);
}
}
}
} for(int i = ; i <= c; i++) {
for(int x = xi[i] - ; x <= xi[i] + ; x++) {
for(int y = yi[i] - ; y <= yi[i] + ; y++) {
int s = get(x, y);
if(cut[s]) {
return ;
}
}
}
}
return ;
} inline void clear() {
mp.clear();
use.clear();
memset(dfn + , , tot * sizeof(int));
memset(low + , , tot * sizeof(int));
memset(cut + , , tot * sizeof(bool));
memset(vis + , , tot * sizeof(int));
memset(vis_c + , , c * sizeof(bool));
tot = ;
num = ;
top = ;
return;
} int main() {
int T;
read(T);
while(T--) {
printf("%d\n", solve());
if(T) {
clear();
}
}
return ;
}
AC代码
找个时间在uoj上A一A。