2015长春网络赛1005
比赛的时候没有把询问排序,每一次都重头合并,结果无限TLE
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,q,d,sum;
struct stu
{
int x,y,l;
};
stu mapp[100010];
int f[20010],root[20010];
struct stu1
{
int x;
int id;
};
stu1 que[5050];
int ans[5050];
bool cmp(stu x,stu y)
{
return x.l<y.l;
}
bool cmp1(stu1 x,stu1 y)
{
return x.x<y.x;
}
void init()
{
for(int i=0;i<20010;i++)
{
f[i]=i;
root[i]=1;
}
}
void input()
{
cin>>n>>m>>q;
for(int i=0;i<m;i++)
{
cin>>mapp[i].x>>mapp[i].y>>mapp[i].l;
}
sort(mapp,mapp+m,cmp);
}
int dfs(int x)
{
if(f[x]!=x) f[x]=dfs(f[x]);
return f[x];
}
void build(int x,int y)
{
if(dfs(x)!=dfs(y))
{
sum+=root[dfs(x)]*root[dfs(y)]*2;
root[dfs(y)]+=root[dfs(x)];
f[dfs(x)]=dfs(y);
}
}
void solve()
{
for(int i=0;i<q;i++) cin>>que[i].x,que[i].id=i;
sort(que,que+q,cmp1);
int k=0;
sum=0;
for(int i=0;i<m;i++)
{
while(mapp[i].l>que[k].x)
{
ans[que[k].id]=sum;
k++;
if(k==q) break;
}
if(k==q) break;
build(mapp[i].x,mapp[i].y);
}
for(int i=k;i<q;i++)
{
ans[que[i].id]=sum;
}
}
void output()
{
for(int i=0;i<q;i++)
{
cout<<ans[i]<<endl;
}
}
int main()
{
cin.sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
init();
input();
solve();
output();
}
return 0;
}