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) 와 함께 나머지 는 읽 기 & 2 점 검색 출력 입 니 다.역시 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
", (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;
}