【NOIP 2018向上組】コース整備
トランスファゲート
problem
C城は一連のレーシングカー試合を開催する.試合前には、城内にm mコースを建設する必要がある.
C城にはn n nの交差点があり、これらの交差点番号は1,2,...,n 1,2,...,n 1,2,...,n,n−1 n−1 n−1コースを建設するのに適した双方向通行の道路があり、各道路は2つの交差点を結んでいる.このうち、i i i番目の道路が接続されている2つの交差点番号はa i a_であるi aiとb i b_i bi、この道路の長さはl i l_i li.このn−1 n−1 n−1の道路により,どの交差点からも他のすべての交差点に到達できる.
1本のコースは互いに異なる道e 1,e 2,...,e k e_1,e_2,…,e_k e 1,e 2,...,ek,満足ある交差点から出発して、順次道路e 1,e 2,...,e k e_1,e_2,…,e_k e 1,e 2,...,ek(各道路を1回通過し、Uターンは許されない)は別の交差点に到達する.1つのコースの長さは通過する各道路の長さの和に等しい.安全を保証するために、各道路が1つのコースによって通過することができることが要求される.
現在、コースの建設案はまだ確定していない.あなたの任務は、建設されたm m mコースの中で最も長さの小さいコースの長さが最大になるように、コースの建設案を設計することです(すなわち、m m mコースの中で最も短いコースの長さができるだけ大きい).
データ範囲:2≦n≦50000 2≦n≦50000 2≦n≦50000、1≦m≦n−1≦m≦n−1≦m≦n−1≦m≦n−1、1≦l i≦10000 1≦l_i ≤ 10000 1≤li≤10000.
solution
この問題の2点は明らかだと思いますが、どうやって答えを検証しますか?
欲張りを考える.現在の2分の1の値をk k kと仮定します.
以下の「一致」は、2つの長さ点u u uについて、私たちはその息子v vを遍歴し、v v vごとにv a l valが返され、v v vの中でマッチングが終わった後に残った最長のエッジを表し、w(u,v)w(u,v)w(u,v)w(u,v)を加えます.
現在の合法的な状況は2つあります v a l ≥ k val\geq k val≥k. v a l a + v a l b ≥ k val_a+val_b\geq k vala+valb≥k.
第1種については,直接a n s++ans++ans++でよい.
2つ目の場合、私たちは一致しなければなりません.私たちはv a l valに従って小さいから大きいまでソートし、v a l valごとに、最初の≧k−v a lgeq k−val≧k−valの鎖を見つけて、それらをつなぎ合わせて、それからa n s++ans++ans++ans++ans++を見つけます.このステップはmultisetでメンテナンスすればいいです.
注意最後に直径を二分の上界として求め、菊花図に引っかからないようにします.
code
problem
C城は一連のレーシングカー試合を開催する.試合前には、城内にm mコースを建設する必要がある.
C城にはn n nの交差点があり、これらの交差点番号は1,2,...,n 1,2,...,n 1,2,...,n,n−1 n−1 n−1コースを建設するのに適した双方向通行の道路があり、各道路は2つの交差点を結んでいる.このうち、i i i番目の道路が接続されている2つの交差点番号はa i a_であるi aiとb i b_i bi、この道路の長さはl i l_i li.このn−1 n−1 n−1の道路により,どの交差点からも他のすべての交差点に到達できる.
1本のコースは互いに異なる道e 1,e 2,...,e k e_1,e_2,…,e_k e 1,e 2,...,ek,満足ある交差点から出発して、順次道路e 1,e 2,...,e k e_1,e_2,…,e_k e 1,e 2,...,ek(各道路を1回通過し、Uターンは許されない)は別の交差点に到達する.1つのコースの長さは通過する各道路の長さの和に等しい.安全を保証するために、各道路が1つのコースによって通過することができることが要求される.
現在、コースの建設案はまだ確定していない.あなたの任務は、建設されたm m mコースの中で最も長さの小さいコースの長さが最大になるように、コースの建設案を設計することです(すなわち、m m mコースの中で最も短いコースの長さができるだけ大きい).
データ範囲:2≦n≦50000 2≦n≦50000 2≦n≦50000、1≦m≦n−1≦m≦n−1≦m≦n−1≦m≦n−1、1≦l i≦10000 1≦l_i ≤ 10000 1≤li≤10000.
solution
この問題の2点は明らかだと思いますが、どうやって答えを検証しますか?
欲張りを考える.現在の2分の1の値をk k kと仮定します.
以下の「一致」は、2つの長さ
現在の合法的な状況は2つあります
第1種については,直接a n s++ans++ans++でよい.
2つ目の場合、私たちは一致しなければなりません.私たちはv a l valに従って小さいから大きいまでソートし、v a l valごとに、最初の≧k−v a lgeq k−val≧k−valの鎖を見つけて、それらをつなぎ合わせて、それからa n s++ans++ans++ans++ans++を見つけます.このステップはmultisetでメンテナンスすればいいです.
注意最後に直径を二分の上界として求め、菊花図に引っかからないようにします.
code
#include
",l);
return 0;
}