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 G with vertex set V=1,2,…,N and a length-N sequence of positive integers D=(D1,D2,…,DN). Here, letting degG(i) denote the degree of vertex i in G, the inequality Di≤degG(i) holds for every vertex i. Also, ∑i=1NDi is even.
- Determine whether it is possible to delete zero or more edges of G so that the degree of every vertex i becomes Di. The answer is
Possibleif this can be done, andImpossibleotherwise.
For S⊆V, define the following.
- eG(S): The number of edges of G with both endpoints in S.
- eG(i,S): The number of edges of G connecting vertex i∈/S to a vertex in S.
Snuke came up with the following conjecture Y about problem X.
The statement "for every subset S of V, (∑i∈SDi)−2eG(S)≤∑i∈/Smin(Di,eG(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 S" must not exceed "the sum, over the vertices outside S, of the maximum number of edges that each of them can have toward S".
However, this conjecture is false.
You are given a length-N sequence of positive integers D, where ∑i=1NDi is even. Determine whether there exists a simple undirected graph G with vertex set V satisfying Di≤degG(i) for every vertex i such that (G,D) is a counterexample to conjecture Y.
You are given T test cases; solve each of them.
考虑如下判定问题 X:
- 给定一个顶点集为 V=1,2,…,N 的简单无向图 G,以及一个长度为 N 的正整数序列 D=(D1,D2,…,DN)。记 degG(i) 为顶点 i 在 G 中的度数,则对每个顶点 i,均满足不等式 Di≤degG(i);此外,∑i=1NDi 为偶数。
- 判断是否可以通过删除 G 中零条或多条边,使得每个顶点 i 的度数恰好变为 Di。若可以实现,则答案为
Possible;否则为Impossible。
对任意子集 S⊆V,定义如下:
- eG(S):G 中两个端点均属于 S 的边的条数;
- eG(i,S):G 中连接顶点 i∈/S 与 S 中某顶点的边的条数。
Snuke 提出了关于问题 X 的如下猜想 Y:
“对 V 的任意子集 S,均有 (∑i∈SDi)−2eG(S)≤∑i∈/Smin(Di,eG(i,S))”
当且仅当 “问题 X 的答案为Possible”。
直观上,该条件表达的是:“必须从 S 内部连出的边数”不能超过“对 S 外每个顶点 i,其能连向 S 的最大边数(即 min(Di,eG(i,S)))之和”。
然而,该猜想是错误的。
给定一个长度为 N 的正整数序列 D,其中 ∑i=1NDi 为偶数。请判断是否存在一个以 V 为顶点集的简单无向图 G,使得对每个顶点 i 均满足 Di≤degG(i),且 (G,D) 构成猜想 Y 的一个反例。
你将收到 T 组测试数据,请对每组数据求解。
输入格式
The input is given from Standard Input in the following format:
T
case1
case2
⋮
caseT
Each test case is given in the following format:
N
D1 D2 … DN
输入从标准输入中按以下格式给出:
T
case1
case2
⋮
caseT
每个测试用例按以下格式给出:
N
D1 D2 … DN
输出格式
For each test case, output Yes if there exists a graph G that is a counterexample to conjecture Y, and No otherwise.
对于每个测试用例,如果存在一个图 G 是猜想 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 G to be the graph consisting of a cycle on vertices 1,2,3 and a cycle on vertices 4,5,6. In this case, for example, for S=1,2,4:
- Left-hand side: (∑i∈SDi)−2eG(S)=(D1+D2+D4)−2×1=1
- Right-hand side: ∑i∈/Smin(Di,eG(i,S))=min(D3,2)+min(D5,1)+min(D6,1)=3
Thus, the inequality in conjecture Y holds. Similarly, the condition can be verified for every subset S.
On the other hand, no matter how the edges of G are deleted, it is impossible to make every vertex have degree 1. Therefore, this G is a counterexample, and the answer is Yes.
Constraints
- 1≤T≤125000
- 2≤N≤250000
- 1≤Di≤N−1 (1≤i≤N)
- ∑i=1NDi is even.
- The sum of N over all test cases in a single input is at most 250000.
- All input values are integers.
样例 1 解释:
在第一个测试用例中,可取图 G 为由顶点 1,2,3 构成的一个环与顶点 4,5,6 构成的另一个环所组成的图。此时,例如对集合 S={1,2,4}:
- 左边:(∑i∈SDi)−2eG(S)=(D1+D2+D4)−2×1=1
- 右边:∑i∈/Smin(Di,eG(i,S))=min(D3,2)+min(D5,1)+min(D6,1)=3
因此,猜想 Y 中的不等式成立。类似地,该条件对每个子集 S 均可验证成立。
另一方面,无论以何种方式删除图 G 的边,都不可能使每个顶点的度数均为 1。因此,该图 G 是一个反例,答案为 Yes。
约束条件
- 1≤T≤125000
- 2≤N≤250000
- 1≤Di≤N−1(1≤i≤N)
- ∑i=1NDi 为偶数。
- 单组输入中所有测试用例的 N 之和不超过 250000。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?