「JoyOI1460」旅行

2014年3月20日4,91611

描述 Description

A国有n座城市，每座城市都十分美，这使得A国的民众们非常喜欢旅行。然而，A国的交通十分落后，这里只有m条双向的道路，并且这些道路都十分崎岖，有的甚至还是山路，只能靠步行。通过每条道路的长度、泥泞程度等因素，我们给每条道路评估一个“崎岖度”，表示通过这条道路的不舒适程度。
从X城市经过若干条道路到达Y城市，我们称这次旅行的“代价”为所经过道路“崎岖度”的最大值。当然，如果从X城市到Y城市有多条路线，民众们会自觉选择“代价”最小的路线进行旅行。但是，A国的民众也是有脾气的，如果旅行的“代价”超过了他们的“忍耐度”，他们就不选择这个旅行了，甚至宁愿在家里宅着。
现在A国的国王想进行若干次询问：给定民众的“忍耐度”，问还有多少对城市(X,Y)会存在旅行？请你对国王的每次询问分别给出回答。

输入格式 InputFormat

第1行三个正整数n、m、Q，分别表示城市数量、道路数量和询问次数。
第2行到第m+1行每行三个正整数x、y、w，表示x号城市和y号城市之间有一条“崎岖度”为w的双向道路。
第m+2行至第m+Q+1行，每行一个正整数k，表示询问中给定的“忍耐度”为k。

输出格式 OutputFormat

共Q行，对于每次询问做出回答。

样例输入 SampleInput [复制数据]

5 5 2

1 2 1

2 3 2

3 4 1

4 5 4

5 1 1

样例输出 SampleOutput [复制数据]

4
10

数据范围和注释 Hint

「样例说明」
第一个询问：(1,2)、(1,5)、(2,5)、(3,4)。其中(2,5)的具体走法为：2-1-5
第二个询问：(1,2)、(1,3)、(1,4)、(1,5)、(2,3)、(2,4)、(2,5)、(3,4)、(3,5)、(4,5)。其中(4,5)的具体走法为：4-3-2-1-5
「数据规模」
对于20%的数据满足n<=20，m<=40，Q<=40；
对于40%的数据满足n<=1000，m<=2000，Q<=1000；
对于60%的数据满足n<=3000，m<=6000，Q<=200000；
对于100%的数据满足n<=100000，m<=200000，Q<=200000。其他数不超过10^9。
「细节提示」
1 给出的n个城市不一定全部互相连通，且两个城市之间可能存在多条道路，也可能存在某条边是从某城市出发回到他自己。
2 对于询问的结果可能很大，请注意使用适当的类型存储。

题解

先从小到大排序然后利用并查集维护连通性更新答案得到由边权划分出的答案表二分查找输出即可。。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,q;
struct data{int x,y,v;}e[200001];
long long f[200001];
int ft[200001],s[200001];
bool cmp(data a,data b)
{return a.v<b.v;}
int find(int x)
{
   if(x==ft[x])return x;
   ft[x]=find(ft[x]);
   s[x]=s[ft[x]];
   return ft[x];
}
void un(int p,int q)
{
	ft[p]=q;
	//cout<<' '<<p<<' '<<q<<' '<<s[q]<<' '<<s[p]<<endl;
	s[q]+=s[p];
}
void ask(int x)
{
	int s=0,l=0,r=m;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(e[mid].v<=x){s=mid;l=mid+1;}
		else r=mid-1;
	}
	printf("%lld\n",f[s]);
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){ft[i]=i;s[i]=1;}
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int p=find(e[i].x),q=find(e[i].y);
	   f[i]=f[i-1];
		if(p!=q)
		{
		f[i]+=s[p]*s[q];
	   un(p,q);
		}
	}
	int x;
	for(int i=1;i<=q;i++)
	{
	   scanf("%d",&x);
	   ask(x);
	}
	return 0;
}