[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
248: 2023/12/22(金)03:32 AAS
マージテクで解けそうじゃね
N-1本の辺にmax(Ai, Aj)のコストを割り振り、コストの昇順にソート
これで「初めてクエリの頂点対が連結になったのはいつ？」という問題に帰着する
各連結成分ごとに連想配列で(クエリの対となる頂点番号、クエリ番号)を保持しておく
辺を追加すると連結成分のマージが発生するが、連結成分数が大きい方から小さい方に連想配列の照会を行う（つまり、クエリの対となる頂点がいるか確認する）
ここではじめて連結になるクエリ対がいれば、このときの追加辺コストが答え
最後に連想配列のマージを行う
計算量が不安だがマージテクでQlogQかNlogNに収まるはず
上下前次1-新書関写板覧索設栞歴
あと 754 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.007s