AT_abc482_g.Degree Harmony 2

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

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

题目描述

You are given a simple undirected graph GG with NN vertices numbered 11 to NN and MM edges. The ii-th edge connects vertices uiu_i and viv_i.
You are also given a sequence of positive integers A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N).
A spanning subgraph G′G' of GG is called a good graph if it satisfies the following condition.

  • For every integer ii with 1≤i≤N1 \leq i \leq N, the degree of vertex ii in G′G' is at most AiA_i.

Find the maximum possible number of edges in a good graph.

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

给你一个包含 NN 个顶点(编号为 11 到 NN)和 MM 条边的简单无向图 GG。第 ii 条边连接顶点 uiu_i 和 viv_i。
同时,你还会得到一个正整数序列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N)。
图 GG 的一个生成子图 G′G' 被称为好图,当且仅当它满足以下条件:

  • 对每个满足 1≤i≤N1 \leq i \leq N 的整数 ii,顶点 ii 在 G′G' 中的度数不超过 AiA_i。

求好图中可能包含的最大边数。

你将收到 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 caset\mathrm{case}_t is given in the following format:

NN MM
A1A_1 A2A_2 …\dots ANA_N
u1u_1 v1v_1
u2u_2 v2v_2
⋮\vdots
uMu_M vMv_M

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

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

每个测试用例 caset\mathrm{case}_t 以如下格式给出:

NN MM
A1A_1 A2A_2 …\dots ANA_N
u1u_1 v1v_1
u2u_2 v2v_2
⋮\vdots
uMu_M vMv_M

输出格式

Print TT lines. The ii-th line should contain the maximum possible number of edges in a good graph for the ii-th test case.

输出 TT 行。第 ii 行应包含第 ii 个测试用例中“好图”可能拥有的最大边数。

输入输出样例

  • 输入#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 11-st test case, the spanning subgraph whose edge set consists of only the 11-st, 33-rd, and 44-th edges is a good graph. No good graph with 44 or more edges can be constructed, so the answer is 33.

Constraints

  • 1≤T≤101 \leq T \leq 10
  • 2≤N≤5002 \leq N \leq 500
  • 1≤M≤N(N−1)21 \leq M \leq \frac{N(N-1)}{2}
  • 1≤Ai≤N−11 \leq A_i \leq N-1
  • ∑i=1NAi≤500\displaystyle \sum_{i=1}^N A_i \leq 500
  • 1≤ui<vi≤N1 \leq u_i \lt v_i \leq N
  • (ui,vi)≠(uj,vj)(u_i, v_i) \neq (u_j, v_j) if i≠ji \neq j.
  • The sum of (∑i=1NAi)3\displaystyle \left(\sum_{i=1}^N A_i\right)^3 over all test cases is at most 5003500^3.
  • The sum of MM over all test cases is at most 2×1052\times 10^5.
  • All input values are integers.

样例 1 解释:
对于第 11 个测试用例,仅包含第 11 条、第 33 条和第 44 条边的生成子图是一个“好图”。无法构造边数 ≥4\geq 4 的“好图”,因此答案为 33。

约束条件

  • 1≤T≤101 \leq T \leq 10
  • 2≤N≤5002 \leq N \leq 500
  • 1≤M≤N(N−1)21 \leq M \leq \frac{N(N-1)}{2}
  • 1≤Ai≤N−11 \leq A_i \leq N-1
  • ∑i=1NAi≤500\displaystyle \sum_{i=1}^N A_i \leq 500
  • 1≤ui<vi≤N1 \leq u_i \lt v_i \leq N
  • 若 i≠ji \neq j,则 (ui,vi)≠(uj,vj)(u_i, v_i) \neq (u_j, v_j)。
  • 所有测试用例中 (∑i=1NAi)3\displaystyle \left(\sum_{i=1}^N A_i\right)^3 的总和不超过 5003500^3。
  • 所有测试用例中 MM 的总和不超过 2×1052\times 10^5。
  • 所有输入值均为整数。

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

首页