文件名称：输入格式-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:33
集训队论文集
1.1 题目简述 给定一张无向简单图 G = (V, E)，设 n = |V |,m = |E|，每个点都有权值，分别为 v1, v2, ..., vn。G 满足一个特殊条件：任取 V 中的 7 个点构成集合 V ′，都存在三个不同的 点 p、q、x满足 p, q ∈ V ′, x ∈ V − {p, q}，使得从图中删去点 x后， p和 q不连通。 现在，给出常数 k，你需要从 G 中找出一个连通的子图 G′ = (V ′, E′)，使得对于任意 p ∈ V ′ 满足 p在 G′ 中的点度不超过 k。要求最大化子图中每个点的权值之和 ∑ p∈V ′ vp（只 需要输出该式子的最大值），并求出能最大化该式子的不同子图个数模 64123。两个子图 G1 = (V1, E1)和 G2 = (V2, E2)不同，当且仅当 V1 , V2 或 E1 , E2。 还需要支持 q次修改，每次修改一个点 p的 vp，请在所有修改之前及每次修改之后都 求出上述两个问题的答案。 1.2 输入格式 第一行包含 3个整数 n,m, k，表示图 G的节点个数、边数及点度限制常数 k； 第二行包含 n个整数 v1, v2, ,, vn，表示每个节点的初始权值； 接下来 m行，其中第 i行包含 2个整数 xi, yi ∈ [1, n]，表示图中的第 i条边连接节点 xi 和节点 yi； 接下来一行包含 1个整数 q，表示修改节点权值的次数； 50