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