集合问题 离线+并查集 HDU 3938

题目大意：给你n个点，m条边，q个询问，每条边有一个val，每次询问也询问一个val，定义：这样条件的两个点(u,v),使得u->v的的价值就是所有的通路中的的最长的边最短。问满足这样的点对有几个。

思路：我们先将询问和边全部都按照val排序，然后我们知道，并查集是可以用来划分集合的，所以我们就用并查集来维护每一个集合就行了。

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

const int maxn = 1e5 + ;

const int maxm = 5e5 + ;

int n, m, Q;

pair<int, pair<int, int> > p[maxm];///边

pair<int, int> q[maxn];///询问

int par[maxn];

LL sum[maxn], ans[maxn];

int pfind(int x){

    if (x == par[x]) return x;

    return par[x] = pfind(par[x]);

}

int main(){

    while (scanf("%d%d%d", &n, &m, &Q) == ){

        for (int i = ; i <= m; i++){

            int u, v, val;

            scanf("%d%d%d", &u, &v, &val);

            p[i] = mk(val, mk(u, v));

        }

        sort(p + , p +  + m);

        memset(sum, , sizeof(sum));

        for (int i = ; i <= n; i++) par[i] = i, sum[i] = ;

        for (int i = ; i <= Q; i++){

            int val; scanf("%d", &val);

            q[i] = mk(val, i);

        }

        sort(q + , q +  + Q);

        int j = ; LL cnt = ;

        for (int i = ; i <= m && j <= Q; ){

            while (i <= m && p[i].first <= q[j].first){

                int pa = pfind(p[i].second.first);

                int pb = pfind(p[i].second.second);

                i++;

                if (pa == pb) continue;

                cnt += sum[pa] * sum[pb];

                ///printf("sum[%d] = %I64d sum[%d] = %I64d\n", pa, sum[pa], pb, sum[pb]);

                par[pa] = pb;

                sum[pb] += sum[pa];

            }

            while (j <= Q && q[j].first < p[i].first){

                ans[q[j].second] = cnt;

                j++;

            }

        }

        while (j <= Q){

            ans[q[j].second] = cnt;

            j++;

        }

        for (int i = ; i <= Q; i++){

            printf("%I64d\n", ans[i]);

        }

    }

    return ;

}