UVa 1265 Tour Belt
問題
重み付き無向グラフG(V, E)が与えられる。
Gの部分グラフS(V', E')であって、
SはV'に含まれる枝は全て含む
(S内の辺の重みの最小値)>(Sの境界の辺の重みの最大値)が成り立つ
ものをtour beltの候補と呼ぶ。
全てのtour beltの候補の頂点数の和を求めよ。
制約条件
n≦5000
m≦n(n-1)/2
方針
tour beltの候補の集合は、入れ子構造になっている。
辺を重い順に見てマージしていく。
マージ後の集合を全て調べれば、tour beltの候補が全て調べられたことになる。
データが弱いらしく、マージ後の集合それぞれが条件を満たすかは、愚直にやって間に合う。
ソースコード
int p[5000]; int root(int x){ return x == p[x] ? x : (p[x] = root(p[x])); } int n, m, mn[5000]; vector<vector<pi> > e; vector<pair<int, pi> > es; int main(){ int cs; cin >> cs; while(cs--){ cin >> n >> m; es.clear(); e.clear(); e.resize(n); rep(i, m){ int a, b, c; cin >> a >> b >> c; es.pb(mp(-c, mp(--a, --b))); e[a].pb(mp(b, c)); e[b].pb(mp(a, c)); } vi vs[5000]; rep(i, n){ p[i] = i; mn[i] = (int)1e9; vs[i].pb(i); } ll ans = 0; sort(all(es)); rep(i, es.size()){ int a = es[i].second.first, b = es[i].second.second; a = root(a); b = root(b); if(a == b) continue; p[b] = a; rep(j, vs[b].size()) vs[a].pb(vs[b][j]); int mx = 0, mn = (int)1e9; rep(j, vs[a].size()){ int v = vs[a][j]; each(k, e[v]){ int to = k->first; if(root(to) != a) mx = max(mx, k->second); else mn = min(mn, k->second); } } if(mx < mn) ans += vs[a].size(); } cout << ans << endl; } return 0; }