AT_abc482_g.Degree Harmony 2
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a simple undirected graph G with N vertices numbered 1 to N and M edges. The i-th edge connects vertices ui and vi.
You are also given a sequence of positive integers A=(A1,A2,…,AN).
A spanning subgraph G′ of G is called a good graph if it satisfies the following condition.
- For every integer i with 1≤i≤N, the degree of vertex i in G′ is at most Ai.
Find the maximum possible number of edges in a good graph.
You are given T test cases; solve each of them.
给你一个包含 N 个顶点(编号为 1 到 N)和 M 条边的简单无向图 G。第 i 条边连接顶点 ui 和 vi。
同时,你还会得到一个正整数序列 A=(A1,A2,…,AN)。
图 G 的一个生成子图 G′ 被称为好图,当且仅当它满足以下条件:
- 对每个满足 1≤i≤N 的整数 i,顶点 i 在 G′ 中的度数不超过 Ai。
求好图中可能包含的最大边数。
你将收到 T 组测试数据;请分别求解每组数据。
输入格式
The input is given from Standard Input in the following format:
T
case1
case2
⋮
caseT
Each test case caset is given in the following format:
N M
A1 A2 … AN
u1 v1
u2 v2
⋮
uM vM
输入从标准输入中以如下格式给出:
T
case1
case2
⋮
caseT
每个测试用例 caset 以如下格式给出:
N M
A1 A2 … AN
u1 v1
u2 v2
⋮
uM vM
输出格式
Print T lines. The i-th line should contain the maximum possible number of edges in a good graph for the i-th test case.
输出 T 行。第 i 行应包含第 i 个测试用例中“好图”可能拥有的最大边数。
输入输出样例
输入#1
3 4 4 2 2 1 1 1 2 1 3 1 4 2 3 6 7 3 3 1 1 1 1 1 2 1 3 1 5 2 3 2 5 3 4 5 6 10 12 1 2 2 1 1 1 1 1 1 1 1 2 1 5 1 8 2 3 2 4 3 4 5 6 5 7 6 7 8 9 8 10 9 10
输出#1
3 3 5
说明/提示
Sample 1 Explanation:
For the 1-st test case, the spanning subgraph whose edge set consists of only the 1-st, 3-rd, and 4-th edges is a good graph. No good graph with 4 or more edges can be constructed, so the answer is 3.
Constraints
- 1≤T≤10
- 2≤N≤500
- 1≤M≤2N(N−1)
- 1≤Ai≤N−1
- i=1∑NAi≤500
- 1≤ui<vi≤N
- (ui,vi)=(uj,vj) if i=j.
- The sum of (i=1∑NAi)3 over all test cases is at most 5003.
- The sum of M over all test cases is at most 2×105.
- All input values are integers.
样例 1 解释:
对于第 1 个测试用例,仅包含第 1 条、第 3 条和第 4 条边的生成子图是一个“好图”。无法构造边数 ≥4 的“好图”,因此答案为 3。
约束条件
- 1≤T≤10
- 2≤N≤500
- 1≤M≤2N(N−1)
- 1≤Ai≤N−1
- i=1∑NAi≤500
- 1≤ui<vi≤N
- 若 i=j,则 (ui,vi)=(uj,vj)。
- 所有测试用例中 (i=1∑NAi)3 的总和不超过 5003。
- 所有测试用例中 M 的总和不超过 2×105。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?