UOJ142 【UER #5】万圣节的南瓜灯题解

题意：

cxy 是~~一个心灵手巧的女孩纸~~。今天是万圣节， cxy 正在家里制作南瓜灯。

这时候一群熊孩子们敲开了 cxy 家的门，他们高呼着 “不用给糖，只要捣蛋” 的口号把 cxy 的南瓜灯弄坏了。这让 cxy 很难过，于是她打算把这些被弄坏的南瓜灯做成其他的工艺品。

cxy 把她的南瓜灯划分成了 $n \times m$ 的网格，并用 $(x,y)$ 表示第 $x$ 行，第 $y$ 列的格子。两个格子是相邻的当且仅当它们有一条公共边，特殊地， $(x,1)$ 和 $(x,m)$ cxy 也视为是相邻的，但是他不把 $(1,x)$ 和 $(n,x)$ 当做是相邻的。

对于一个有 $k$ 个格子被弄坏的南瓜灯，如果它能被制作成工艺品，当且仅当对于任意两个没有被弄坏的格子，都存在且仅存在一条连接它们的简单路径。一条简单路径定义为一个只包含没有被弄坏的格子的序列 $A_1$ 至 $A_n$ ，其中对于任意的 $1 \leq i < n$ 都有 $A_i$ 和 $A_{i+1}$ 是相邻的，且每一个格子在序列中至多出现了一次。

现在 cxy 有 $T$ 个南瓜灯，她想让你帮她分别判断每一个南瓜灯能不能被做成工艺品。

输入格式：

第一行一个正整数 $T$，表示南瓜灯数目。

对于每一个南瓜灯，第一行是三个整数 $n,m,k$，表示南瓜灯的大小和被弄坏的格子数。

接下来 $k$ 行每行包含两个整数 $x,y$（$1 \leq x \leq n,1 \leq y \leq m$），表示第 $x$ 行第 $y$ 列的格子被弄坏了。

数据保证 $n,m \geq 3$，$0 \leq k < nm$ 且不会重复描述一个被弄坏的格子。

输出格式：

对于每一个南瓜灯，输出一行，如果这个南瓜灯能被做成工艺品，那么输出 “Yes”，否则输出”No”。

数据范围：

$n,m \le 10^9,~k\le 10^5$

直接暴力建图坑定是不行滴。

但是我们可以从 $k$ 的范围估测出有效点数

因为当点数很多的时候，很难产生一棵树，因此这一定有个上界

点数很简单，肯定是 $|V|=nm-k$

考虑边数，$nm$ 条横向边 + $(n-1)m$ 条纵向边 = $(2n-1)m$ 条边

而每次删掉一条边至多删去 $4$ 条边，故

$|E| \ge (2n-1)m - 4k$

由于 $|E|=|V|-1$ ，则

$nm-k-1 \ge (2n-1)m-4k$

即

$3k \ge (n-1)m+1$

如果不满足这个条件直接输出No就好了

你看这个 $(n-1)$ ，~~是不是很难看~~，于是尝试要找到 $n$ 与 $n-1$ 的关系

~~离谱的来了~~

$n\ge 3 \Rightarrow n \le \dfrac{3}{2} (n-1)$

因此

$|V| < nm \le \dfrac{3}{2}(n-1)m < \dfrac{9}{2}k \le 4.5\times 10^5$

于是直接 $\mathtt{dfs}$ 就好啦！

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(5e5+15))
#define cxy static int x;
#define is for(int i=1; i<=k; i++)
#define very cin >> x >> x;
#define cute return 0
#define haha(r,c) ((r-1) * m + c)
const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
int n,m,k,used[N],ck[N];
bool dfs(int x,int y,int la=0)
{
    int cur=haha(x,y),tx,ty,nx;
    used[cur] = 1;
    for(int d=0; d<4; d++)
    {
        tx=x+dx[d]; ty=(y+dy[d]+m-1) % m + 1; nx=haha(tx,ty);
        if(tx >= 1 && tx <= n && !ck[nx] && nx!=la)
            if(used[nx] || !dfs(tx,ty,cur)) return 0;
    }
    return 1;
}
bool work()
{
    cin >> n >> m >> k; int i,j=0;
    if(3 * k <= (n-1) * m) {cxy is very cute;}
    memset(used,0,sizeof(used));
    memset(ck,0,sizeof(ck));
    for(int i=1,u,v; i<=k; i++) cin >> u >> v,ck[haha(u,v)] = 1;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
            if(!ck[haha(i,j)] && !used[haha(i,j)])
                {if(!dfs(i,j)) return 0; else break;} // find a root
        if(j<=m) break;
    } 
    for(i=haha(i,j); i<=n*m; i++)
        if(!ck[i] && !used[i]) return 0; // can't reach
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q;for(cin >> Q; Q--; ) cout << (work() ? "Yes\n" : "No\n");
    return 0;
}