hdu 4750 Count The Pairs (2013南京网络赛)
n个点m条无向边的图，对于q个询问，每次查询点对间最小瓶颈路 >=f 的点对有多少。
最小瓶颈路显然在kruskal求得的MST上。而输入保证所有边权唯一，也就是说f[i][j]肯定唯一了。
拿到这题第一反映是用次小生成树的prim算法在求MST的同时求出每对点对的瓶颈路。几乎就是一个模板题，无奈却MLE。。。
于是换算法，用kruskal求MST，然后对于MST，离线LCA求出所有点对的瓶颈路。同UVA 11354 Bond（MST + LCA）然后剩下的就是读入&二分查找输出了。。无奈还是MLE！！！
最后。。。反思了一下。。。在kruskal的过程，当前加入的边必定是新图中最大的边！也就是说，每次加入一条边，求出当前图中经过该边的点对数就行了。。。求一个图中经过该边的点对数，将该边割开，分别从两个端点dfs，左边能遍历到x个点，右边能遍历到y个点，那么点对数就是x*y了。
原图不连通的情况也是存在的吧，这个几乎对算法不影响，只需在进入MST的点数==n的时候终止函数就行了。
#include<algorithm>#include<iostream>#include<cstring>#include<fstream>#include<sstream>#include<vector>#include<string>#include<cstdio>#include<bitset>#include<queue>#include<stack>#include<cmath>#include<map>#include<set>#define FF(i, a, b) for(int i=a; i<b; i++)#define FD(i, a, b) for(int i=a; i>=b; i--)#define REP(i, n) for(int i=0; i<n; i++)#define CLR(a, b) memset(a, b, sizeof(a))#define LL long long#define PB push_back#define eps 1e-10#define debug puts("**debug**")using namespace std;const int maxn = 10010;const int maxm = 555555;const int INF = 1e9;int n, m, dfs_clock, q, f, cnt, fa[maxn];LL sum[maxn*2];bool seen[maxn];vector<int> edge;struct E{ int u, v, w; E(){} E(int u, int v, int w) : u(u), v(v), w(w){} bool operator < (const E& rhs) const { return w < rhs.w; }}e[maxm]; //kruskal的边vector<int> G[maxn]; //dfs用inline void add(int a, int b){ G[a].PB(b); G[b].PB(a);}int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }void dfs(int u, int fa){ dfs_clock++; REP(i, G[u].size()) { int v = G[u][i]; if(v != fa) dfs(v, u); }}void MST(){ int ret = 0; cnt = 1; sum[0] = 0; CLR(seen, 0); sort(e, e+m); REP(i, m) { int x = findset(e[i].u), y = findset(e[i].v); if(x != y) { //统计进入森林的点数 if(!seen[e[i].u]) ret++; if(!seen[e[i].v]) ret++; seen[e[i].u] = 1; seen[e[i].v] = 1; fa[x] = y; add(e[i].u, e[i].v); //将边切割双向统计两边点数 dfs_clock = 0; dfs(e[i].u, e[i].v); int a = dfs_clock; dfs_clock = 0; dfs(e[i].v, e[i].u); int b = dfs_clock; //edge保存所有MST中边 sum[i]为前i条边和 edge.PB(e[i].w); sum[cnt] = sum[cnt-1] + a*b; cnt++; } if(ret == n) return ; //终止MST } return ;}void solve(){ scanf("%d", &q); while(q--) { scanf("%d", &f); int t = lower_bound(edge.begin(), edge.end(), f) - edge.begin(); //找到f的lower_bound 答案便是总和减去小于f的点对和 注意乘以2 printf("%lld\n", (sum[cnt-1]-sum[t])*2); }}int main(){ while(~scanf("%d%d", &n, &m)) { REP(i, n) G[i].clear(), fa[i] = i; edge.clear(); REP(i, m) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w); MST(); solve(); } return 0;}