TopCoder SRM 711 Div2 Hard TreeMovingDiv2
問題概要
与えられた引数にしたがって， 頂点数が n の m 個の木を構築します．
それぞれの木を T(i) とします．
各 i = 0, 1, ..., m-1 について，辺 e(i) ∈ T(i) を一つ選びます．
e(i) を T(i) から取り除き，T(i+1) に加えます．T(m-1) のものは T(0) に加えます．
この操作を行った後，すべての T(i) がまだ木であるような操作の仕方は何通りありますか．
1e9+7 で割った余りを求めなさい．
・ 制約
2 <= n <= 50
2 <= m <= 50
解法
m, n の制約が緩いので，愚直な DP で通ります．
dp[i][j][k] := i 番目の木から j 番目の辺を選び，かつ 0 番目の木からは k 番目の辺を選んでいた場合の数
とします．
あとは，T(i) に対して，T(i-1) の j 番目の辺を選んだときに，T(i) で k 番目の木を選んだ場合，T(i) が木になっているかを Union-find 木で確認します．
木になっていれば，各 l に対して dp[i][k][l] += dp[i-1][j][l] とすればよいです．
最後に，0 番目の木に戻ってきたときは処理が特別になります．
dp[0][i][i] を一旦 0 に戻します．
同じように j, k を選んだ時に，木になっていれば，今度は各 l に対してではなく，k のみ dp[i][k][k] += dp[i-1][j][k]; とします．
こうしないと，最初に k 番目の辺を選んでいたのに，違う辺を選んでいた場合の数が含まれてしまうためです．
あとは，dp[0][i][i] の総和を取れば，答えになります．
計算量は O(mn^3 * (union-findの分)) です．
ソースコード
#include <iostream> #include <vector> #include <cmath> using namespace std; // // union_find の実装は本質でないので省略 // using ll = long long; using edge = pair<int, int>; constexpr ll mod = 1e9+7; class TreeMovingDiv2 { public: int count(int n, vector<int> roots, vector<int> a, vector<int> b, vector<int> c) { const int m = roots.size(); vector<vector<edge>> es(m, vector<edge>(n-1)); for(int i=0; i<m; ++i) { vector<int> x(n-1); x[0] = c[i]; for(int k=1; k<n-1; ++k) { x[k] = ((ll)a[i] * x[k-1] + b[i]) % mod; } for(int j=0; j<n-1; ++j) { es[i][j].first = ((ll)roots[i] + j + 1) % n; es[i][j].second = ((ll)roots[i] + (x[j] % (j+1))) % n; } } vector<vector<vector<ll>>> dp(m+1, vector<vector<ll>>(n-1, vector<ll>(n-1))); for(int i=0; i<n-1; ++i) { dp[0][i][i] = 1; } for(int i=0; i<m; ++i) { int next = (i + 1) % m; if(next == 0) { for(int j=0; j<n-1; ++j) { dp[0][j][j] = 0; } } for(int j=0; j<n-1; ++j) { int prev_v = es[i][j].first, prev_u = es[i][j].second; for(int k=0; k<n-1; ++k) { union_find uf(n); uf.unite(prev_v, prev_u); for(int l=0; l<n-1; ++l) { if(k == l) { continue; } uf.unite(es[next][l].first, es[next][l].second); } if(uf.size(prev_v) == n) { if(next == 0) { (dp[next][k][k] += dp[i][j][k]) %= mod; } else { for(int l=0; l<n-1; ++l) { (dp[next][k][l] += dp[i][j][l]) %= mod; } } } } } } ll res = 0; for(int i=0; i<n-1; ++i) { (res += dp[0][i][i]) %= mod; } return res; } };
感想
本番で通せそうで時間が足りなかった問題．全完したかった．
しかしこれ，入力に悪意があって，木の構築段階で int だとオーバーフローするような入力があるくせに，関数定義は vector(int) を強制されてます．嫌がらせかな？？？
Div 1 の 1 <= n <= 300 だと O(n^3) ってことなんだろうけど，方法が全然わからない．
TopCoder SRM 709 Div2 Med Permatchd2
問題概要
「グラフが "pretty" である」を，「グラフに含まれる任意の連結成分 S に対して，|E(S)| が偶数である」と定義する．
ここで，単純グラフが1つ与えられる．このグラフを "pretty" なものにするためには，辺を最小で何本追加すればよいか求めよ．
どのようにしても "pretty" にできない場合は，-1 とせよ．
・制約
1 <= |V(G)| <= 50
G は単純グラフである．
解法
まず，各連結成分に対して，頂点数と辺数を求めておく．これはDFSで十分．
偶数のものはそのままでよいので，奇数のものについて考える．
まず，|E(S)| が奇数となる連結成分 S の中に，辺を追加できるならそれが最適であることは明らかである．
よって，それが可能であるなら前もって追加して，偶数の連結成分にしておく．以下はそれを前提とする．
S の中に辺を追加できないのは，S が完全グラフである場合である．
残った奇数の連結成分（すべて完全グラフ）は，それらを環状に結べば全体として偶数にできる．
1つしか残らなかった場合は，偶数の連結成分と一本の辺を追加して結べば良い．
1つしか残らず，かつ偶数の連結成分が0個だった場合は，どうやっても無理なので -1 を返す．
ソースコード
#include <vector> #include <string> #include <algorithm> using namespace std; class Permatchd2 { public: int fix(vector<string> graph) { vector<bool> used(graph.size()); vector<pair<int, int>> v; for(int i=0; i<graph.size(); ++i) { if(!used[i]) { int v_cnt = 0, e_cnt = 0; dfs(graph, i, v_cnt, e_cnt, used); e_cnt /= 2; v.push_back(make_pair(v_cnt, e_cnt)); } } int res = 0; int odd_num = 0; for(int i=0; i<v.size(); ++i) { int v_cnt = v[i].first, e_cnt = v[i].second; if(v_cnt*(v_cnt-1)/2 != e_cnt && e_cnt % 2 == 1) { res++; v[i].second += 1; } odd_num += v[i].second % 2 == 1; } if(odd_num == 1) { res = -1; } else { res += odd_num; } return res; } void dfs(vector<string> const& g, int v, int& v_cnt, int& e_cnt, vector<bool>& used) { used[v] = true; v_cnt += 1; e_cnt += count(g[v].begin(), g[v].end(), 'Y'); for(int i=0; i<g[v].size(); ++i) { if(used[i]) { continue; } if(g[v][i] == 'Y') { dfs(g, i, v_cnt, e_cnt, used); } } } };
Codeforces Round #406 (div.2) C
問題概要
円上に n 個のマスがある．それぞれ 0 から n-1 まで番号が振られている．
0 番目はブラックホールである．
また，どこかのマスに一匹のモンスターがいる．
これらを使って2人でゲームをする．2人はそれぞれ集合S1, S2を持っていて，要素はいくつかの自然数である．
順番に，自分の集合の中から好きな数字をえらんで，モンスターを今いる位置から時計回りに選んだ数字分移動させる．この時，ちょうどブラックホールにモンスターを移動させたほうが勝ちである．
モンスターの初期位置が 1, 2, …, n-1 番目のマスだった場合，2人のプレイヤーが最善を尽くした時に先手（プレイヤーは二人いるので2通り）は「勝ち」「ループ」「負け」のいずれになるかをすべて答えよ．
・制約
2 <= n <= 7000
1 <= |Si| <= n-1, for i = 1, 2
解法
典型DP．ゲームなので，最終状態からさかのぼっていくというのが定石．
手番とモンスターの位置で，2*n の状態が存在する．
dp[i][j] := 先手が i 人目で，モンスターの初期位置が j マス目だったときの先手の結果 とする．
dp[1][0] = dp[0][0] = (負け) としておく．
(手番, モンスター位置) = (0, 0) と (1, 0) を根とするDFSをやる．（BFSでも良い．そっちのほうが多かったように思う．）
今見ている状態が負けであれば，一つ前の状態（手番が入れ替わる）は勝ちと決まる．
どのように遷移しても相手が勝ってしまう（すべての次の状態が勝ち）ならば，今の状態を負けとする．
なので，今見ている状態が勝ちであれば，一つ前の状態の勝ちうる遷移の数を一つ減らす．遷移の方法は，自分の持っている自然数の集合のサイズ分あるが，これが0になってしまった場合は，先ほど述べた自分の負けの状態である．
DFSで次に探索しようとしている状態が勝ちとも負けとも今の段階で決められない場合は，そこで探索を保留する．
最終的に，勝ちとも負けとも決まらなかった状態は，ループの状態である．（勝てないのは明らかなので，負けるよりも無限ループさせるほうが最善手となる．）
計算量は O(n^2)．
ソースコード
#include <iostream> #include <vector> using namespace std; constexpr int INF = 1e9; int n; // -1: current turn lose, 1: win, 0: visited(and not determined) void dfs(int turn, int p, vector<vector<int>>& dp, vector<vector<int>>& cnt, vector<vector<int>> const& s) { if(dp[turn][p] == INF) { dp[turn][p] = 0; } for(auto x : s[turn^1]) { int np = (p - x + n) % n; if(dp[turn^1][np] != INF) { continue; } if(dp[turn][p] == -1) { dp[turn^1][np] = 1; } else if(--cnt[turn^1][np] == 0) { dp[turn^1][np] = -1; } else { continue; } dfs(turn^1, np, dp, cnt, s); } } int main() { cin >> n; vector<vector<int>> s(2); for(int i=0; i<2; ++i) { int k; cin >> k; s[i].resize(k); for(int j=0; j<k; ++j) { cin >> s[i][j]; } } vector<vector<int>> dp(2, vector<int>(n, INF)); vector<vector<int>> cnt(2, vector<int>(n)); for(int i=0; i<2; ++i) { for(int j=0; j<n; ++j) { cnt[i][j] = s[i].size(); } } dp[0][0] = dp[1][0] = -1; dfs(0, 0, dp, cnt, s); dfs(1, 0, dp, cnt, s); for(int i=0; i<2; ++i) { for(int j=1; j<n; ++j) { int r = dp[i][j]; if(r == -1) { cout << "Lose"; } else if(r == 1) { cout << "Win"; } else { cout << "Loop"; } cout << " \n"[j == n-1] << flush; } } }
感想
最初，根を適当に選んで DFS していたせいで，ループをうまく扱えなくて困っていた．
こういうコードなんだけども，(DFS 部のみ抜粋）
int dfs(int p, vector<vector<int>>& dp, vector<vector<int>> const& s, int turn) { int& r = dp[turn][p]; if(r != INF) { return r; } if(p == 0) { return r = -1; } r = 0; int t = 2; for(int i=0; i<s[turn].size(); ++i) { t = min(t, dfs((p+s[turn][i])%n, dp, s, (turn+1)%2)); } return r = -t; }
これだと以下の図のようなケース（不必要な辺は省いています）で死にます．
左下の状態は最終的に負けになって欲しいところですが，上のコードだとそうならない．
方針はわかってるのに解ききれなかったのは悔しい．
AOJ 1337 Count the Regions
問題概要
xy 平面に長方形が N 個与えられる．長方形によっていくつの領域に分かれるか求めよ．
・制約
1 <= N <= 50
長方形がある x, y 座標は 0 <= x, y <= 10^6
解法
N が小さいので座標圧縮と確信できる．
与えられた座標を2倍して持っておくと，幅が1しかない領域を数えるのが楽になる．（たとえば，3と4は2倍するとそれぞれ6と8になるので，3と4の間として7を使える．vectorで圧縮後の平面を持つのでこうしておくと便利．）
ソースコード
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; using P = pair<int, int>; int main() { int n; while(cin >> n, n) { vector<int> xs, ys; vector<int> x1(4*n), x2(4*n), y1(4*n), y2(4*n); for(int i=0; i<n; ++i) { int l, t, r, b; cin >> l >> t >> r >> b; l *= 2; t *= 2; r *= 2; b *= 2; x1[i*4] = l, x2[i*4] = r, y1[i*4] = t, y2[i*4] = t; x1[i*4+1] = l, x2[i*4+1] = l, y1[i*4+1] = b, y2[i*4+1] = t; x1[i*4+2] = r, x2[i*4+2] = r, y1[i*4+2] = b, y2[i*4+2] = t; x1[i*4+3] = l, x2[i*4+3] = r, y1[i*4+3] = b, y2[i*4+3] = b; for(int j=-1; j<=1; ++j) { xs.push_back(l+j); xs.push_back(r+j); ys.push_back(t+j); ys.push_back(b+j); } } sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); for(int i=0; i<4*n; ++i) { x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin(); x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin(); y1[i] = find(ys.begin(), ys.end(), y1[i]) - ys.begin(); y2[i] = find(ys.begin(), ys.end(), y2[i]) - ys.begin(); } int res = 0; vector<vector<bool>> fld(ys.size(), vector<bool>(xs.size(), false)); for(int i=0; i<4*n; ++i) { for(int y=y1[i]; y<=y2[i]; ++y) { for(int x=x1[i]; x<=x2[i]; ++x) { fld[y][x] = true; } } } for(int i=0; i<ys.size(); ++i) { for(int j=0; j<xs.size(); ++j) { if(fld[i][j]) { continue; } fld[i][j] = true; res++; queue<P> que; que.push(make_pair(i, j)); while(!que.empty()) { P p = que.front(); que.pop(); int sy = p.first, sx = p.second; int dy[4] = {0, -1, 0, 1}, dx[4] = {1, 0, -1, 0}; for(int k=0; k<4; ++k) { int ty = sy + dy[k], tx = sx + dx[k]; if(ty < 0 || ys.size() <= ty || tx < 0 || xs.size() <= tx) { continue; } if(fld[ty][tx]) { continue; } que.push(make_pair(ty, tx)); fld[ty][tx] = true; } } } } cout << res << endl; } }
AOJ 2302 On or Off
問題概要
R * C のグリッドが与えられる．各マスは，部屋または壁を表している．
さらに，M 個の仕事が与えられて，それぞれの仕事をする部屋は決められている．仕事は与えられた順番にこなす必要がある．
部屋には電気のスイッチがあって，部屋に入るためには電気をつけなければならない．
部屋から出るときは，電気を消すか，つけっぱなしにするか選ぶことができる．ただし，全ての仕事を終えた時，全ての部屋の電気は消されていなければならない．
電気をつける時のコスト，消す時のコスト，つけっぱなしにしたときの単位時間あたりのコストが与えられる．
このとき，全ての仕事を片付けるのに，消費電力を最小化したい．
最小化した時の消費電力を求めよ．
・制約
1 <= R <= 50
1 <= C <= 50
2 <= M <= 1000
任意の2つの部屋を結ぶ道は，ただひとつしかない（つまり部屋は木構造になっている）． ←冒頭にさらっと書かれているが重要な制約．見落とさないように！
（コストの制約が書かれていないが，求める答えは int の表現幅を超えないとして良いようだ）
解法
BFS(経路復元あり) + 貪欲？
木構造になっている条件を見逃すと，僕のように時間を浪費するので気をつけたい．
木構造になっているので，最初の仕事をしてから最後の仕事をするまでの道筋が一意に定まる．
なので，各部屋を訪れる時刻が一意に定まる．（別の時刻に同じ部屋を通ることもある．）
あとでどの部屋を通ったのかを調べないといけないので，経路復元用のデータを作る必要がある．
さて，ある部屋を1度しか通らない場合は，最終的に消えていないといけないので，つけるコスト＋消すコストでよい．
同じ部屋を2回以上通る場合，前回通った時につけっぱなしにすべきかどうかの選択をしなければならない．
ある部屋を i 回目に通った時刻が t[i] で， i-1 回目に通った時刻が t[i-1] だとする．
i-1 回目につけっぱなしにしていれば，(単位時間コスト) * (t[i] - t[i-1]) だけコストがかかり，消していれば再度つけて消すので (つけるコスト) + (消すコスト) がかかる．
これらのうち小さいほうを複数回通るたびに貪欲に選んでいけばよい．
計算量は O(RCM)．
ソースコード
#include <iostream> #include <vector> #include <queue> using namespace std; using P = pair<int, int>; constexpr int INF = 1e9; int main() { int R, C, M; cin >> R >> C >> M; vector<string> v(R); for(int i=0; i<R; ++i) { cin >> v[i]; } // 0: per, 1: on, 2: off vector<vector<vector<int>>> cost(3, vector<vector<int>>(R, vector<int>(C))); for(int i=0; i<3; ++i) { for(int j=0; j<R; ++j) { for(int k=0; k<C; ++k) { cin >> cost[i][j][k]; } } } vector<P> task(M); for(int i=0; i<M; ++i) { cin >> task[i].first >> task[i].second; } int res = cost[1][task[0].first][task[0].second] + cost[2][task[0].first][task[0].second]; vector<vector<int>> prev_t(R, vector<int>(C, INF)); prev_t[task[0].first][task[0].second] = 0; int t = 0; for(int i=1; i<M; ++i) { queue<P> que; que.push(task[i-1]); vector<vector<int>> d(R, vector<int>(C, INF)); vector<vector<P>> prev(R, vector<P>(C, P{-1, -1})); d[task[i-1].first][task[i-1].second] = t; while(!que.empty()) { P p = que.front(); que.pop(); int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; for(int j=0; j<4; ++j) { int nr = p.first + dr[j], nc = p.second + dc[j]; if(nr < 0 || R <= nr || nc < 0 || C <= nc || v[nr][nc] == '#') { continue; } if(d[nr][nc] == INF) { d[nr][nc] = d[p.first][p.second] + 1; prev[nr][nc] = p; que.push(make_pair(nr, nc)); } } } int r = task[i].first, c = task[i].second; t = d[r][c]; while(r != task[i-1].first || c != task[i-1].second) { if(prev_t[r][c] != INF) { res += min((d[r][c] - prev_t[r][c]) * cost[0][r][c], cost[1][r][c] + cost[2][r][c]); } else { res += cost[1][r][c] + cost[2][r][c]; } prev_t[r][c] = d[r][c]; P p = prev[r][c]; r = p.first, c = p.second; } } cout << res << endl; }
感想
AOJ 2156 Magic Slayer
問題概要
N 体のモンスターがいる．それぞれの体力は HP_i である．
自分が使える単体魔法と全体魔法がM個与えられる．それぞれの魔法には消費MPとダメージ量が決まっている．
この時，敵を全滅させるのに必要な最小のMPを求めよ．
・制約
1 <= N <= 100
1 <= HP_i <= 10^5
1 <= M <= 100
0 <= MP_j <= 99
0 <= damage_j <= 999999
解法
典型DP．この問題は実質ドラクエの「まんたん」と同じ．
まず，単体魔法しか無い場合は，それぞれの敵に対して個別にDPすればいいというのはすぐ分かる．
最終的に単体魔法だけ考えればいいことにできれば楽．なので，先に全体魔法によってあるダメージを与えるときに必要な最小のMPを求めておく．
cost[0][i] := 単体魔法だけ用いたときに，i 以上のダメージを与えるために必要な最小のMP．
cost[1][i] := 全体魔法だけ用いたときに，ちょうど i のダメージを与えるために必要な最小のMP．
これらを前計算しておけば，「ちょうど i だけ全体魔法でダメージを与えたときに，全滅させるのに必要な最小MP」は，「全体の体力から i だけ引いた後，単体魔法だけで全滅させるのに必要な最小MP」となるので，ここまでくればあとはやるだけ．
計算量は O((N+M)HP)．
全部が全体（ないし単体）魔法のケース（1WA食らった．if で対処）や，単体魔法はあるけど全てダメージ0の場合（1WA食らった．ダメージ0の魔法をあらかじめ取り除くことで対処）などのコーナーケースに注意しよう．
ソースコード
#include <iostream> #include <vector> #include <string> #include <cmath> using namespace std; using P = pair<int, int>; constexpr int INF = 1e9; int main() { int N; while(cin >> N, N) { vector<int> hp(N); int max_hp = 0; for(int i=0; i<N; ++i) { cin >> hp[i]; max_hp = max(max_hp, hp[i]); } int M; cin >> M; vector<vector<P>> s(2); for(int i=0; i<M; ++i) { string name, target; int mp, dam; cin >> name >> mp >> target >> dam; if(dam == 0) { continue; } s[target == "All"].emplace_back(mp, dam); } vector<vector<int>> cost(2, vector<int>(max_hp+1, INF)); cost[0][0] = cost[1][0] = 0; for(int k=0; k<2; ++k) { for(int i=0; i<s[k].size(); ++i) { for(int j=0; j<=max_hp; ++j) { int t = min(max_hp, j+s[k][i].second); cost[k][t] = min(cost[k][t], cost[k][j] + s[k][i].first); } } } for(int j=max_hp; j>=1; --j) { cost[0][j-1] = min(cost[0][j-1], cost[0][j]); } if(s[0].size() == 0) { cout << cost[1][max_hp] << endl; } else { int res = INF; for(int i=0; i<=max_hp; ++i) { if(cost[1][i] == INF) { continue; } int t = cost[1][i]; for(int j=0; j<N; ++j) { int rest_hp = hp[j] - i; if(rest_hp <= 0 || cost[0][rest_hp] == INF) { continue; } t += cost[0][rest_hp]; } res = min(res, t); } cout << res << endl; } } }
TopCoder SRM 710 Div2 Hard MinMaxMax
問題概要
頂点数 N, 辺の数がM の連結グラフが与えられる．
それぞれの頂点と辺には重みがつけられていて，i 番目の頂点の重みは vi, i 番目の頂点の重みは wi である．
異なる2つの頂点 u, v の間のコストを，u-v パスのうちで，(パスに含まれる頂点の重さの最大値) * (パスに含まれる辺の重さの最大値) の最小値と定義する．
各 (u, v) に対するコストの総和を求めよ．
・制約
2 <= N <= 300
N-1 <= M <= min(2500, N(N-1)/2)
1 <= wi <= 10^6
1 <= vi <= 10^6
多重辺やループは存在しない．
解法の前に
自分は，最初「ワーシャルフロイドの要領でやるんだろうな～」と思って色々考えてみたものの，実装方針が思いつかず，普段理解せずに使ってたんだなぁと痛感した．（結局解けなかった）．
writer解では2つのアプローチが紹介されていて，1つめは Kruskal 法の要領でやっていくもので，2つめはワーシャルフロイドの要領でやっていくものだった．
両方記事にしたいけど，まとめると長いので2つに分ける．
今回は1つ目のアプローチを実装した．
解法1
頂点の重みと辺の重みのどちらも考える必要があるので大変．（単純に，ある頂点に来るための最小コストだけを保存していくような最短経路問題ではない）．
なので，とりあえず頂点の最大の重みを固定してしまってから考えると良い．これを vmax とする．
その上で，辺の重みが小さい順にソートしておいて，小さい方から追加していく．この時，辺を追加することで結ばれた連結成分を union-find 木で保存しておく（Kruskal 法と同じ）．
追加したい辺が頂点 ai と bi を結んでいたとする．
ai と bi がすでに同じ連結成分に含まれれば，その辺は無視できる（より小さい辺のみでつながっている）．また，ai と bi の重みのどちらかが vmax を超えても，その辺を無視する．
それ以外の場合，その辺を追加する．
この時，ai の連結成分 S1 と，bi の連結成分 S2 の各頂点間 (s, t) (s ∈ S1, t ∈ S2) のコストは vmax * (今追加した辺の重み) 以下となることがわかる．なぜなら，S1 と S2 に含まれる頂点の重みは全て vmax 以下であり，かつ今までに追加した全ての辺の重みは，今追加した辺の重みよりも小さいからである．
よって，vmax * (今追加した辺の重み) と，今までにわかっている (s, t) 間の最小コストとを比べて，小さい方を保存しておけばよい．
これを vmax を N 個の頂点で全部試せば，目的の値が得られる．
計算量は O(N^2M) か？これはちょっと自信がない（連結成分のコスト更新の二重ループのコストがピンとこない．下のコードでいうと，va と vb でループを回しているところ．）
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; using P = pair<ll, ll>; constexpr ll INF = 1e18; class union_find { public: union_find(int n) : par_(n, -1) {} void init(int n) { par_.assign(n, -1); } int root(int x) { return par_[x] < 0 ? x : par_[x] = root(par_[x]); } bool unite(int x, int y) { x = root(x); y = root(y); if(x == y) { return false; } else { if(par_[x] < par_[y]) { // size(x) > size(y) par_[x] += par_[y]; par_[y] = x; } else { par_[y] += par_[x]; par_[x] = y; } return true; } } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return -par_[root(x)]; } private: std::vector<int> par_; }; class MinMaxMax { public: ll findMin(vector<int> a, vector<int> b, vector<int> w, vector<int> v) { const int N = v.size(), M = w.size(); vector<vector<ll>> d(N, vector<ll>(N, INF)); vector<P> ww(M); for(int i=0; i<M; ++i) { ww[i] = make_pair(w[i], i); } sort(ww.begin(), ww.end()); for(int i=0; i<N; ++i) { vector<int> comp(N); union_find uf(N); for(int j=0; j<M; ++j) { int aa = a[ww[j].second], bb = b[ww[j].second]; if(uf.same(aa, bb) || v[i] < v[aa] || v[i] < v[bb]) { continue; } ll now = v[i] * ww[j].first; vector<int> va, vb; for(int k=0; k<N; ++k) { if(uf.same(k, aa)) { va.push_back(k); } else if(uf.same(k, bb)) { vb.push_back(k); } } for(int k=0; k<va.size(); ++k) { for(int l=0; l<vb.size(); ++l) { int ca = va[k], cb = vb[l]; d[ca][cb] = min(now, d[ca][cb]); d[cb][ca] = min(now, d[cb][ca]); } } uf.unite(aa, bb); } } ll res = 0; for(int i=0; i<N; ++i) { for(int j=i+1; j<N; ++j) { res += d[i][j]; } } return res; } };
解法2
わかりやすい記事があったので，引用して終わりとします．
kmjp.hatenablog.jp
