← 返回题目列表

AtCoder · arc009_4

D. 觉醒高桥君

中文机器翻译题面 查看原题

問題文

AtCoder国家有很多城镇。
城市是城镇的集合,其存在是为了管理城镇。
城内各乡镇均有公路相连。这些道路可通往市内所有城镇。
但是,您无法仅使用这些道路前往其他城市的城镇。
因此,在AtCoder的国家,为了解决这个问题,一些城镇由多个城市管理,并且城市之间相互连接,使得所有城市之间的出行成为可能。

管理一个城镇和多个城市是非常麻烦的,因此共享位置的数量要尽可能少。
具体来说, 假设有 N 个城市, k 个城市共享的城镇数量为 S_k 它变成 Σ(S_k×(k-1))=N-1 。

高桥先生是AtCoder国家的国土交通大臣,他希望尽可能降低开发每条道路的总成本。
然而,维护计划 1 我担心, k 我决定想出最好的计划。

计划内容如下。
  • 在任何城镇之间旅行时,路线应准确无误 我想维护它,以便建立 1 。
  • 发展道路意味着减少城镇之间的道路数量。
他意识到有很多计划符合这个标准。
因此,我们决定该计划的成本是开发每条道路的总成本。
成本值越低,计划越好。

k 打印第一个最佳计划的成本。 如果第k个值不存在,则 打印-1。

入力

输入是按以下格式从标准输入给出的。 添加了约束
A T k
N_1
C_{11} C_{12} C_{13} ... C_{1N_1}
:
:
N_A
C_{N1} C_{N2} C_{N3} ... C_{NN_A}
M
city_{11} city_{12} cost_1
:
:
cost_{M1} city_{M2} cost_M
  • 输入是 有一行 2×A+M+2 。
  • 1 行中城市数量 A(1≦A≦77) , 城镇数量 T(1≦T≦A×7) ,一个非负整数 k(1≦k≦7,777,777) 。
  • 2 从行 2×A+1 至行 2×A 行提供有关属于该城市的城镇的信息。 表示属于第
    1. N_i(2≦N_i≦7) ... i 个城市的城镇数量。 属于第
    2. C_{ij}(1≦C_{ij}≦T) ... i 个城市 代表第 j 个城镇。
  • M 表示道路数量,为非负整数。直到输入结束 M 行给出道路信息。
    1. city_{i1} 和 city_{i2} 是 i 代表由道路连接的城镇。换句话说, city_{i1} 和 city_{i2} 可双向移动,属于同一城市。
    2. cost_i(1≦cost_i≦77) 是 i 表示开发道路所需的成本。

出力

k打印第一个最佳计划的成本。 如果第k个值不存在,则 打印-1。

入力例 1

3 7 1
3
1 2 3
3
3 4 5
3
5 6 7
9
1 2 1
1 3 2
2 3 3
3 4 3
3 5 6
4 5 9
5 6 9
5 7 18
6 7 27
図:入力例 1 的插图

出力例 1

13
図:出力例 1 状态的图示
  • 1 最好的计划是 1 和镇 2 连接的道路和城镇 3 和镇 4 连接的道路和城镇 5 和镇 6 这是一项拆除连接它们的道路的计划。

入力例 2

2 3 2
2
1 2
2
2 3
2
1 2 1
2 3 1

出力例 2

-1
  • 2 由于最佳计划没有成本, -1 。

入力例 3

4 9 2
3
1 2 3
3
3 4 5
3
5 6 7
3
5 8 9
12
1 2 1
1 3 1
2 3 1
3 4 3
3 5 3
4 5 3
5 6 6
5 7 3
6 7 9
5 8 9
5 9 18
8 9 27

出力例 3

16
  • 总成本为 16 的计划是最小的,但有 9 个计划具有相同的成本。因此,第二个方案所需的成本也是16。