icontofig | 发布于 2019-02-27 00:17:20 | 阅读量 152 | 并查集

## 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.

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

```2
6
12```

## 题目大意

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

## 题解

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;
}﻿​```

152 人读过

0 条评论