第 009 场 AtCoder Regular Contest
NAI (CI翻译)
觉醒的高桥君AI (CI翻译)
N
k
kAI (CI翻译)
S_k
S_kAI (CI翻译)
Σ(S_k×(k-1))=N-1
Σ(S_k×(k-1))=N-1AI (CI翻译)
1
1AI (CI翻译)
k
kAI (CI翻译)
- どの町の間を移動する場合にも、同じ町を重複して通らないように移動したとき、経路がちょうど
$1$つに定まるように整備したいです。 - 道を整備するとは、町と町の間の道を減らすことである。
- 我们希望整备道路，使得无论在任意两个城镇之间移动，只要移动过程中不重复经过同一个城镇，路径都能恰好确定为
$1$条。 - 所谓整备道路，是指减少城镇之间的道路数量。
k
kAI (CI翻译)
k
kAI (CI翻译)
-1
-1AI (CI翻译)
制約の追記を行いました
补充了约束条件AI (CI翻译)
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_MA 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$行は市に所属する町の情報が与えられる。$M$は道の数を表し、非負の整数である。入力の最後までの$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$行，给出属于各城市的城镇信息。 $M$表示道路数量，是一个非负整数。从输入末尾开始的$M$行给出道路信息。
k
kAI (CI翻译)
k
kAI (CI翻译)
-1
-1AI (CI翻译)
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 273 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 的示意图AI (CI翻译)
1313
図：出力例 $1$ の状態を図示したもの
图：输出样例 1 中状态的示意图AI (CI翻译)
$1$番目に良いプランは、町$1$と 町$2$を繋ぐ道、町$3$と町$4$を繋ぐ道、町$5$と町$6$を繋ぐ道を取り除いたプランです。
- 第
$1$优的方案，是移除连接城镇$1$与城镇$2$、连接城镇$3$与城镇$4$、连接城镇$5$与城镇$6$的道路的方案。
2 3 2
2
1 2
2
2 3
2
1 2 1
2 3 12 3 2
2
1 2
2
2 3
2
1 2 1
2 3 1-1-1$2$番目に良いプランのコストが存在しないため、-1を出力します。
- 由于不存在第
$2$优方案的成本，因此输出-1。
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 274 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 271616- 合計コストが16のプランが最小ですが、これと同じコストで出来るプランは9通り存在します。よって、2番目のプランの必要コストも同じく16です。
- 总成本为 16 的方案是最优的，但存在 9 个总成本同样为 16 的方案。因此，第
$2$优方案所需的成本同样为 16。
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。