PKU 2832 How Many Pairs?
http://poj.org/problem?id=2832
グラフが与えられる。
このとき、max_len(p)をパスpに含まれる辺のコストの最大値
min_pair(u,v)をmin{max_len(p) | pはu,vを結ぶパス}と定義したときに、
ある値aに対してmin_pair(u,v)<=aとなるような、u,vの組みはいくつかを答えろというような問題。
クエリを小さい順にソートして、最小全域木をサイズを管理しながらユニオンファインドで作っていけばよい。
親を取って来るべきところを失敗したり、cinつかって1WA1TLE
int un[10000]; int ch[10000]; int find(int x){ if(x==un[x]) return x; return un[x] = find(un[x]); } void unit(int a,int b){ int ap=find(a); int bp=find(b); un[ap] = bp; ch[bp] += ch[ap]; } main(){ ios::sync_with_stdio(false); int n,m,q; cin >> n >> m >> q; rep(i,n){ un[i] = i; ch[i] = 1; } vector<pair<int,PI> > ed(m); rep(i,m){ int a,b,c; cin >> a >> b >> c; --a,--b; ed[i]=mp(c,mp(a,b)); } sort(ALL(ed)); vector<PI> qu(q); rep(i,q){ cin >> qu[i].F; qu[i].S=i; } sort(ALL(qu)); ll ans=0; ll out[q]; int idx=0; rep(i,q){ //cout << qu[i].F << ' ' << qu[i].S << endl; while(idx<m && ed[idx].F<=qu[i].F){ int a=ed[idx].S.F; int b=ed[idx].S.S; if(find(a) != find(b)){ ans += ch[find(a)] * ch[find(b)]; unit(a,b); } ++idx; } out[qu[i].S] = ans; } rep(i,q) cout << out[i] << endl; }