AT_agc079_d.Yet Another Degree Sequence Problem

NOI/NOI+/CTSC

通过率:0%

时间限制:8.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Consider the following decision problem X.

  • You are given a simple undirected graph GG with vertex set V=1,2,…,NV={1,2,\ldots,N} and a length-NN sequence of positive integers D=(D1,D2,…,DN)D=(D_1,D_2,\ldots,D_N). Here, letting deg⁡G(i)\deg_G(i) denote the degree of vertex ii in GG, the inequality Di≤deg⁡G(i)D_i\leq \deg_G(i) holds for every vertex ii. Also, ∑i=1NDi\sum_{i=1}^N D_i is even.
  • Determine whether it is possible to delete zero or more edges of GG so that the degree of every vertex ii becomes DiD_i. The answer is Possible if this can be done, and Impossible otherwise.

For S⊆VS\subseteq V, define the following.

  • eG(S)e_G(S): The number of edges of GG with both endpoints in SS.
  • eG(i,S)e_G(i,S): The number of edges of GG connecting vertex i∉Si\notin S to a vertex in SS.

Snuke came up with the following conjecture Y about problem X.

The statement "for every subset SS of VV, (∑i∈SDi)−2eG(S)≤∑i∉Smin⁡(Di,eG(i,S))\left(\sum_{i\in S}D_i\right)-2e_G(S)\leq \sum_{i\notin S}\min(D_i,e_G(i,S)) holds" is equivalent to the statement "the answer to problem X is Possible".

Intuitively, the condition says that "the number of edges that must leave SS" must not exceed "the sum, over the vertices outside SS, of the maximum number of edges that each of them can have toward SS".

However, this conjecture is false.

You are given a length-NN sequence of positive integers DD, where ∑i=1NDi\sum_{i=1}^N D_i is even. Determine whether there exists a simple undirected graph GG with vertex set VV satisfying Di≤deg⁡G(i)D_i\leq\deg_G(i) for every vertex ii such that (G,D)(G,D) is a counterexample to conjecture Y.

You are given TT test cases; solve each of them.

考虑如下判定问题 X:

  • 给定一个顶点集为 V=1,2,…,NV={1,2,\ldots,N} 的简单无向图 GG,以及一个长度为 NN 的正整数序列 D=(D1,D2,…,DN)D=(D_1,D_2,\ldots,D_N)。记 deg⁡G(i)\deg_G(i) 为顶点 ii 在 GG 中的度数,则对每个顶点 ii,均满足不等式 Di≤deg⁡G(i)D_i\leq \deg_G(i);此外,∑i=1NDi\sum_{i=1}^N D_i 为偶数。
  • 判断是否可以通过删除 GG 中零条或多条边,使得每个顶点 ii 的度数恰好变为 DiD_i。若可以实现,则答案为 Possible;否则为 Impossible。

对任意子集 S⊆VS\subseteq V,定义如下:

  • eG(S)e_G(S):GG 中两个端点均属于 SS 的边的条数;
  • eG(i,S)e_G(i,S):GG 中连接顶点 i∉Si\notin S 与 SS 中某顶点的边的条数。

Snuke 提出了关于问题 X 的如下猜想 Y:

“对 VV 的任意子集 SS,均有 (∑i∈SDi)−2eG(S)≤∑i∉Smin⁡(Di,eG(i,S))\left(\sum_{i\in S}D_i\right)-2e_G(S)\leq \sum_{i\notin S}\min(D_i,e_G(i,S))”
当且仅当 “问题 X 的答案为 Possible”。

直观上,该条件表达的是:“必须从 SS 内部连出的边数”不能超过“对 SS 外每个顶点 ii,其能连向 SS 的最大边数(即 min⁡(Di,eG(i,S))\min(D_i,e_G(i,S)))之和”。

然而,该猜想是错误的。

给定一个长度为 NN 的正整数序列 DD,其中 ∑i=1NDi\sum_{i=1}^N D_i 为偶数。请判断是否存在一个以 VV 为顶点集的简单无向图 GG,使得对每个顶点 ii 均满足 Di≤deg⁡G(i)D_i\leq\deg_G(i),且 (G,D)(G,D) 构成猜想 Y 的一个反例。

你将收到 TT 组测试数据,请对每组数据求解。

输入格式

The input is given from Standard Input in the following format:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

Each test case is given in the following format:

NN
D1D_1 D2D_2 …\ldots DND_N

输入从标准输入中按以下格式给出:

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每个测试用例按以下格式给出:

NN
D1D_1 D2D_2 …\ldots DND_N

输出格式

For each test case, output Yes if there exists a graph GG that is a counterexample to conjecture Y, and No otherwise.

对于每个测试用例,如果存在一个图 GG 是猜想 Y 的反例,则输出 Yes;否则输出 No。

输入输出样例

  • 输入#1

    8
    6
    1 1 1 1 1 1
    6
    2 2 2 2 2 2
    2
    1 1
    7
    1 1 1 1 1 1 2
    7
    2 2 2 2 2 2 6
    8
    2 2 2 2 2 2 2 2
    9
    2 2 2 2 2 2 2 2 2
    10
    2 2 3 3 3 3 3 3 9 9

    输出#1

    Yes
    No
    No
    Yes
    Yes
    No
    Yes
    Yes

说明/提示

Sample 1 Explanation:
In the first test case, you can take GG to be the graph consisting of a cycle on vertices 1,2,31,2,3 and a cycle on vertices 4,5,64,5,6. In this case, for example, for S=1,2,4S={1,2,4}:

  • Left-hand side: (∑i∈SDi)−2eG(S)=(D1+D2+D4)−2×1=1\left(\sum_{i\in S}D_i\right)-2e_G(S) = (D_1+D_2+D_4)-2 \times 1 = 1
  • Right-hand side: ∑i∉Smin⁡(Di,eG(i,S))=min⁡(D3,2)+min⁡(D5,1)+min⁡(D6,1)=3\sum_{i\notin S}\min(D_i,e_G(i,S)) = \min(D_3,2)+\min(D_5,1)+\min(D_6,1)=3

Thus, the inequality in conjecture Y holds. Similarly, the condition can be verified for every subset SS.

On the other hand, no matter how the edges of GG are deleted, it is impossible to make every vertex have degree 11. Therefore, this GG is a counterexample, and the answer is Yes.

Constraints

  • 1≤T≤1250001\leq T\leq 125000
  • 2≤N≤2500002\leq N\leq 250000
  • 1≤Di≤N−11\leq D_i\leq N-1 (1≤i≤N)(1\leq i\leq N)
  • ∑i=1NDi\sum_{i=1}^N D_i is even.
  • The sum of NN over all test cases in a single input is at most 250000250000.
  • All input values are integers.

样例 1 解释:
在第一个测试用例中,可取图 GG 为由顶点 1,2,31,2,3 构成的一个环与顶点 4,5,64,5,6 构成的另一个环所组成的图。此时,例如对集合 S={1,2,4}S = \{1,2,4\}:

  • 左边:(∑i∈SDi)−2eG(S)=(D1+D2+D4)−2×1=1\left(\sum_{i\in S}D_i\right)-2e_G(S) = (D_1+D_2+D_4)-2 \times 1 = 1
  • 右边:∑i∉Smin⁡(Di,eG(i,S))=min⁡(D3,2)+min⁡(D5,1)+min⁡(D6,1)=3\sum_{i\notin S}\min(D_i,e_G(i,S)) = \min(D_3,2)+\min(D_5,1)+\min(D_6,1)=3

因此,猜想 Y 中的不等式成立。类似地,该条件对每个子集 SS 均可验证成立。

另一方面,无论以何种方式删除图 GG 的边,都不可能使每个顶点的度数均为 11。因此,该图 GG 是一个反例,答案为 Yes。

约束条件

  • 1≤T≤1250001\leq T\leq 125000
  • 2≤N≤2500002\leq N\leq 250000
  • 1≤Di≤N−11\leq D_i\leq N-1(1≤i≤N1\leq i\leq N)
  • ∑i=1NDi\sum_{i=1}^N D_i 为偶数。
  • 单组输入中所有测试用例的 NN 之和不超过 250000250000。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页