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;
}