记录编号	58347	评测结果	AAAAAAAAAA
题目名称	威尼斯旅行	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	1.074 s
提交时间	2013-04-19 15:49:05	内存使用	9.97 MiB

#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
class adjtype
{
public:
	int u,v;
	long long w;
}adj[200001];
int n,m,q;
class cc
{
public:
	int ii;
	long long k;	
}quest[200001];
long long ans[200001],sum;
bool oj(adjtype a1,adjtype a2)
{
	if(a1.w<a2.w)return 1;
	return 0;
}
bool op(cc t1,cc t2)
{
	if(t1.k<t2.k)return 1;
	return 0;
}
class set//并查集的集合C
{
public:
	int parent;
	long long number;//count有几层,parent记录父亲节点,number记录这颗树总共有多少节点
}C[100001];
void makeset(int x)//集
{
	C[x].parent=-1;
	C[x].number=1;
}
int findset(int x)//查+压缩路径
{
	int y=x,z=x,tmp;
	while(C[z].parent!=-1)z=C[z].parent;
	while(C[y].parent!=-1)tmp=y,y=C[y].parent,C[tmp].parent=z;//路径压缩
	return z;
}
void merge(int x,int y)//并
{
	if(x==y)return;
	C[x].parent=y;
	C[y].number+=C[x].number;
}
int main()
{
	freopen("tripa.in","r",stdin);
	freopen("tripa.out","w",stdout);
	int i,j,k,l;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%lld",&adj[i].u,&adj[i].v,&adj[i].w);
	}
	sort(adj+1,adj+m+1,oj);
	for(i=1;i<=q;i++)//将查询的k值读入并排序
	{
		scanf("%lld",&quest[i].k);
		quest[i].ii=i;//记录排序前的标号
	}
	sort(quest+1,quest+q+1,op);
	quest[0].k=0;
	//======================================================处理读入
	for(i=1;i<=n;i++)makeset(i);
	j=1;sum=0;
	for(i=1;i<=q;i++)
	{
		while(j<=m&&adj[j].w<=quest[i].k)//没有用过这条边而且可以加进去
		{
			k=findset(adj[j].u);
			l=findset(adj[j].v);
			if(k!=l)
			{
				sum=sum-C[k].number*(C[k].number-1)/2-C[l].number*(C[l].number-1)/2;
				merge(k,l);
				sum+=C[l].number*(C[l].number-1)/2;
			}
			j++;
		}
		//---------------------------------------------------
		ans[quest[i].ii]=sum;
	}
	for(i=1;i<=q;i++)printf("%lld\n",ans[i]);
	//======================================================_=
	return 0;
}