城市路径伤害
gouyiming200802 · · 个人记录
英文题面
City Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2583 Accepted Submission(s): 247
Problem Description Lucida occupies n cities connected by m undirected roads, and each road has a strength ki. The enemy will attack to destroy these roads. When the enemy launches an attack with damage x, all roads with strength less than x will be destroyed.
Now Lucida has Q questions to ask you, how many pairs of cities are reachable to each other if the enemy launches an attack with damage pi. City x and city y are reachable, which means that there is a path from x to y, and every road's strength in that path is greater than or equal to pi.
Input This problem contains multiple test cases.
The first line contains a single integer T (1≤T≤10).
Then T test cases follow.
For each test case, the first line contains 3 integers n,m,Q (2≤n≤105, 1≤m≤2×105, 1≤Q≤2×105), which represent the number of cities, the number of roads, and the number of queries.
The next m lines, each line contains three integers x,y,k (1≤x,y≤n, 1≤k≤109), which represent the road connecting city x and city y, and the strength of this road is k.
The next Q lines, each line contains an integer pi (1≤pi≤109), asking how many pairs of cities are reachable to each other if the enemy launches an attack with damage pi.
Output Output ∑T1Q lines, each line contains an integer, representing the answer for each question.
Sample Input 1 5 5 3 1 2 2 2 3 3 3 4 1 4 5 1 5 1 3 3 2 1
Sample Output 2 6 10
中文题面
城市
时间限制：6000/3000毫秒（Java/其他）内存限制：65536/65536 K（Java/其他）
申请总数：2583份接受申请：247份
问题描述
卢西达占据了由m条无向道路连接的n个城市，每条道路都有一个强度ki。敌人将进攻摧毁这些道路。当敌人发动伤害为x的攻击时，所有强度小于x的道路都将被摧毁。
现在露西达有Q个问题要问你，如果敌人以伤害pi发动攻击，有多少对城市彼此可以到达。城市x和城市y是可到达的，这意味着有一条从x到y的路径，该路径中每条道路的强度大于或等于pi。
输入
此问题包含多个测试用例。
第一行包含一个整数T（1≤T≤10).
然后，T测试用例随之出现。
对于每个测试用例，第一行包含3个整数n，m，Q（2≤N≤105, 1≤M≤2×105, 1≤Q≤2×105），表示城市数量、道路数量和查询数量。
接下来的m行，每行包含三个整数x，y，k（1≤x、 y≤n、 一,≤K≤109），表示连接x市和y市的道路，该道路的强度为k。
接下来的Q行，每行包含一个整数pi（1≤圆周率≤109），询问如果敌人发动攻击并造成pi伤害，有多少对城市可以相互接近。
输出
输出∑T1Q行，每行包含一个整数，表示每个问题的答案。
样本输入
1
5 5 3
1 2 2
2 3 3
3 4 1
4 5 1
5 1 3
3
2
1
样本输出
2
6
10
CCPC的一道图论，实质考察的是并查集。
由于本题没有要求在线回答，因此可以对于每一个询问按照伤害从大到小降序排
列，这样可以保证越往后的询问只会向其中加入路径而不会删除路径，保证了并查
集算法的可行性，对于每一条路径的存储，没有必要使用链式前向星，直接用三元
结构体即可。因为是取最大值，可以使用priority_queue的STL大根堆来实现操作，
然后就是并查集的基本操作超级简单，答案的统计比较繁琐，对于每一个并查集，
对答案的贡献是n
sum=sum-(siz[fy]*(siz[fy]-1)/2)-(siz[fx]*(siz[fx]-1)/2);
siz[fy]+=siz[fx];
sum+=siz[fy]*(siz[fy]-1)/2;总的来说，就是先删除分段，再加入总体超级好想
#include<bits/stdc++.h>
#define MAXN 200006
using namespace std;
int T,n,m,Qy;
int ans[MAXN*2],fa[MAXN*2],siz[MAXN*2];
struct kl{
int x;
int y;
int k;
};
bool operator <(kl x,kl y){
return x.k<y.k;
}
struct kk{
int num;
int hur;
};
bool operator <(kk x,kk y){
return x.hur<y.hur;
}
priority_queue<kl>q;
priority_queue<kk>Q;
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
int main(){
scanf("%d",&T);
while(T--){
memset(ans,0,sizeof(ans));
memset(fa,0,sizeof(fa));
memset(siz,0,sizeof(siz));
scanf("%d %d %d",&n,&m,&Qy);
for(int i=1;i<=m;i++){
kl t;
scanf("%d %d %d",&t.x,&t.y,&t.k);
q.push(t);
}
for(int i=1;i<=Qy;i++){
kk p;
scanf("%d",&p.hur);
p.num=i;
Q.push(p);
}
for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
int pos=0,tot=0,sum=0;
while(!Q.empty()){
kk x=Q.top();Q.pop();
while(!q.empty()){
kl y=q.top();
if(y.k>=x.hur){
q.pop();
int fx=find(y.x);
int fy=find(y.y);
if(fx==fy)continue;
fa[fx]=fy;
sum=sum-(siz[fy]*(siz[fy]-1)/2)-(siz[fx]*(siz[fx]-1)/2);
siz[fy]+=siz[fx];
sum+=siz[fy]*(siz[fy]-1)/2;
}
else break;
}
ans[x.num]=sum;
}
for(int i=1;i<=Qy;i++){
printf("%d\n",ans[i]);
}
}
return 0;
}