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;

}


  

?

?

hdu 4750 Count The Pairs (2013南京網絡賽)