L - Two Pseudoforests
Assam
6
s
1024
MB
700
点
問題文
$N$ 頂点 $M$ 辺の単純無向グラフ $G$ が与えられます。頂点と辺にはそれぞれ、頂点 $1,2,\dots,N$、辺 $1,2,\dots,M$ と番号が付けられており、辺 $i\ (1\leq i\leq M)$ は頂点 $U_i$ と $V_i$ を結んでいます。はじめ、全ての辺は白く塗られています。
以下の条件を全て満たすグラフを良いグラフと定義します。
- $G$ の全ての頂点と全ての赤い辺からなる部分グラフは擬似森である。
- $G$ の全ての頂点と全ての青い辺からなる部分グラフは擬似森である。
あなたは以下のいずれかの操作を $0$ 回以上行うことができます。
- 白く塗られている辺を $1$ つ選び、赤く塗る。ただし、この操作によってグラフが良いグラフでなくなってはならない。塗った辺が辺 $i$ であれば、この操作によってあなたはスコア $R_i$ を得る。
- 白く塗られている辺を $1$ つ選び、青く塗る。ただし、この操作によってグラフが良いグラフでなくなってはならない。塗った辺が辺 $i$ であれば、この操作によってあなたはスコア $B_i$ を得る。
得られるスコアの総和の最大値を求めてください。
擬似森とは
無向グラフであって、各連結成分ごとの閉路の個数が高々 $1$ であるもの。制約
すべてのテストケースについて、以下の制約を満たす。
- 入力はすべて整数
- $2\leq N\leq 1000$
- $1\leq M\leq 1000$
- $1\leq U_i\leq N\ (1\leq i\leq M)$
- $1\leq V_i\leq N\ (1\leq i\leq M)$
- $1\leq R_i\leq 10^9\ (1\leq i\leq M)$
- $1\leq B_i\leq 10^9\ (1\leq i\leq M)$
- 与えられるグラフは単純
部分点
この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。
- ($100$ 点)
- $N \leq 10$
- $M \leq 10$
- ($600$ 点)
- 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$
$U_1$ $V_1$ $R_1$ $B_1$
$U_2$ $V_2$ $R_2$ $B_2$
$\vdots$
$U_M$ $V_M$ $R_M$ $B_M$
出力
得られるスコアの総和の最大値を出力せよ。
入力例 1
6 9
1 2 1 9
2 3 2 8
3 1 3 7
2 4 4 6
4 5 5 5
5 2 6 4
3 5 7 3
5 6 8 2
6 3 9 1
出力例 1
65
たとえば、辺 $5,6,7,8,9$ を赤く塗り、辺 $1,2,3,4$ を青く塗る操作を順に行うのが最適です。このとき得られるスコアの総和は $65$ です。
この入力は、部分点 1., 2.の制約を満たします。
入力例 2
6 6
1 2 1 1000000000
2 3 1 1000000000
3 1 1 1000000000
4 5 1 1000000000
5 6 1 1000000000
6 4 1 1000000000
出力例 2
6000000000
全ての辺を青く塗るのが最適です。
この入力は、部分点 1., 2.の制約を満たします。
入力例 3
5 10
1 2 3 14
1 3 15 9
1 4 2 65
1 5 35 8
2 3 9 79
2 4 32 3
2 5 8 46
3 4 26 4
3 5 3 38
4 5 32 7
出力例 3
382
この入力は、部分点 1., 2.の制約を満たします。