记录编号	58284	评测结果	AAAAAAAAAA
题目名称	威尼斯旅行	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	2.326 s
提交时间	2013-04-18 21:34:44	内存使用	14.72 MiB

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("tripa.in");
ofstream fo("tripa.out");
long long n,m,q,fu[100001],ceng[100001],ans,s,num[100001],out[200001];
class t
{
public:
	long long way,begin,end;
};
class t2
{
public:
	long long k,yuan;
};
t a[200001];
t2 yun[200001];
void init()
{
	int i,y,u,o;s=0;
	fi>>n>>m>>q;
	for (i=1;i<=m;i++)
	{
		fi>>y>>u>>o;
		if (y!=u) {a[++s].begin=y;a[s].end=u;a[s].way=o;}
	}
	for (i=1;i<=q;i++) {fi>>yun[i].k;yun[i].yuan=i;}
	for (i=1;i<=n;i++) {ceng[i]=1;fu[i]=i;num[i]=1;}
}
int zx(int x)
{
	if (fu[x]!=x) return zx(fu[x]);
	return x;
}
void hebing(int x,int y)
{
	if (ceng[x]>ceng[y]) {fu[y]=x;num[x]+=num[y];}else
	{
		fu[x]=y;num[y]+=num[x];
		if (ceng[x]==ceng[y]) ceng[y]++;
	}
}
bool cmp(t x,t y)
{
	if (x.way<y.way) return true;else return false;
}
bool cmp2(t2 x,t2 y)
{
	if (x.k<y.k) return true;else return false;
}
int main()
{
	int i,j=0,x,y;
	init();
	sort(a+1,a+s+1,cmp);
	sort(yun+1,yun+q+1,cmp2);
	for (i=1;i<=q;i++)
	{
		while (j<=s)
		{
			if (a[j+1].way<=yun[i].k)
			{
				j++;
				x=zx(a[j].begin);
				y=zx(a[j].end);
				if (x!=y)
				{
					ans+=num[x]*num[y];
					hebing(x,y);
				}
			}else break;
		}
		out[yun[i].yuan]=ans;
	}
	for (i=1;i<=q;i++) fo<<out[i]<<endl;
	return 0;
}