HDU-5441 Travel 贪心+加权并查集

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

Descrpition

Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are n cities and m bidirectional roads connecting the cities. Jack hates waiting too long on the bus, but he can rest at every city. Jack can only stand staying on the bus for a limited time and will go berserk after that. Assuming you know the time it takes to go from one city to another and that the time Jack can stand staying on a bus is x minutes, how many pairs of city (a,b) are there that Jack can travel from city a to b without going berserk?

Input

The first line contains one integer T,T≤5 , which represents the number of test case.

For each test case, the first line consists of three integers n,m and q where n≤20000,m≤100000,q≤5000 . The Undirected Kingdom has n cities and m bidirectional roads, and there are q queries.

Each of the following m lines consists of three integers a,b and d where a,b∈{1,...,n} and d≤100000 . It takes Jack d minutes to travel from city a to city b and vice versa.

Then q lines follow. Each of them is a query consisting of an integer x where x is the time limit before Jack goes berserk.

Output

You should print q lines for each test case. Each of them contains one integer as the number of pair of cities (a,b) which Jack may travel from a to b within the time limit x. Note that (a,b) and (b,a) are counted as different pairs and a and b must be different cities.

Sample Input

1
5 5 3
2 3 6334
1 5 15724
3 5 5705
4 3 12382
1 3 21726
6000
10000
13000

Sample Output

2
6
12

题目大意

Jack要旅游,他在这个王国中坐车旅游,然而他能承受的一次性的坐车时间是有限的,每次乘坐汽车从一个城市到相连的另一个城市的时间不超过他能承受的一次性坐车时间他才能从这个城市转移到另一个城市(即路径上的距离最大值不能超过Jack的承受极限),给出Jack的承受极限,问他最多可以穿梭多少个城市组合(a->b 与b->a并非一个组合)


题解

警告!这个题不是最短路!别看错题意!
题目中要求的是只要这条路径上的距离最大值不超过承受极限即可,于是这道题和最短路半毛钱关系都没有。
我们可以把路径长度和Jack的承受极限(也就是询问)分别从小到大排序,然后按照排序后的询问贪心地加边维护图。维护图的连通性直接使用并查集,不过在维护连通性的同时,这道题还要维护并查集每个根节点连通的节点个数(相当于加权并查集?)
如果当前加入的边的两个端点城市a,b不在同一个并查集中,就合并两个并查集,并计算出新的并查集的节点个数
num[find(a)] += num[find(b)],
维护答案:
ans += (num[find(a)]+num[find(b)])(num[find(a)]+num[find(b)]-1) - num[find(a)](num[find(a)]-1) - num[find(b)]*num[find(b)-1],
最后再按照询问的给出顺序输出答案即可。


代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 20005;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (((num<<2)+num)<<1) + c - '0';
    return(flag ? -1 : 1) * num;
}
struct edge{
    int w,fr,to;
    bool operator < (const edge &a)const{
        return w < a.w;
    }
}e[(maxn<<2)+maxn];
struct problem{
    int id;
    int x;
    int ans;
}q[maxn];
bool cmp1(problem a,problem b){
    return a.x < b.x;
}
bool cmp2(problem a,problem b){
    return a.id < b.id;
}
int f[maxn],num[maxn];
int n,m,T;
int qn;
void init(){
    for(int i = 1;i <= n;++i){
        f[i] = i;
        num[i] = 1;
    }
    memset(e,0,sizeof(e));
    memset(q,0,sizeof(q));
    return;
}
int find(int x){
    if(f[x] != x)f[x] = find(f[x]);
    return f[x];
}
int tmp;
int main(){
    T = get_num();
    while(T--){
        n = get_num();
        m = get_num();
        qn = get_num();
        tmp = 0;
        init();
        for(int i = 1;i <= m;++i){
            e[i].fr = get_num();
            e[i].to = get_num();
            e[i].w = get_num();
        }
        sort(e+1,e+m+1);
        for(int i = 1;i <= qn;++i){
            q[i].id = i;
            q[i].x = get_num();
        }
        sort(q+1,q+qn+1,cmp1);
        int pos = 1;
        for(int i = 1;i <= qn;++i){
            while(pos <= m && e[pos].w <= q[i].x){
                int x = find(e[pos].fr);
                int y = find(e[pos].to);
                pos++;
                if(x == y)continue;
                tmp += (num[x] + num[y]) * (num[x] + num[y] - 1) - num[x]*(num[x] - 1) - num[y] * (num[y] - 1);
                if(num[x] < num[y])swap(x,y);
                f[y] = x;
                num[x] += num[y];
            }
            q[i].ans = tmp;
        }
        sort(q+1,q+qn+1,cmp2);
        for(int i = 1;i <= qn;++i)
            printf("%d\n",q[i].ans);
    }
    return 0;
}​
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00