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;
}