问题 A: Travel
时间限制: 1 Sec 内存限制: 512 MB题目描述
输入
4 4 4
1 2 1
2 3 3
3 4 2
4 1 4
3 2
3 3
3 1
3 4
1 2 1
2 3 3
3 4 2
4 1 4
3 2
3 3
3 1
3 4
输出
2
4
1
4
4
1
4
提示
干找会超时。。可以利用刚刚做过的魔法森林的思路，因为对于一个询问的len，只可以走边权<=它的，因此把询问的len去重后按大小排序，每次只建边权小于等于它的边。更新询问的答案。
其实这样还会超时，所以不用建边了，用并查集的思想，把每个连通块合并在一起，记录size，size由最顶端祖先记录，查询时只要找此节点祖先的size就行了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define N 100000
using namespace std;
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}return sum*f;
}
struct road
{int v,next,l;
} lu[4*N+5];
struct node
{int u,v,l;
} f[4*N+5];
struct Q
{int id,x,len;
} q[N+5];
int n,m,k,adj[N+5],e,A[N+5],sz,sum;
int ans[N+5],hh[N+5],fa[N+5];
void add(int u,int v,int l){lu[++e].v=v;lu[e].l=l;lu[e].next=adj[u];adj[u]=e;}
inline bool cmp(const Q &a,const Q &b){return a.len<b.len;}
inline bool cmp1(const node &a,const node &b){return a.l<b.l;}
int find(int x)
{if(fa[x]==x)return x;fa[x]=find(fa[x]);return fa[x];
}
void hb(int x,int y)
{int x1=find(x),y1=find(y);if(x1!=y1){fa[x1]=y1,hh[y1]+=hh[x1];}
}
int main()
{//freopen("travel.in","r",stdin);//freopen("travel.out","w",stdout);n=read();m=read();k=read();int x,y,z;for(int i=1;i<=m;i++){f[i].u=read();f[i].v=read();f[i].l=read();}for(int i=1;i<=k;i++){q[i].x=read();q[i].len=read();q[i].id=i;A[i]=q[i].len;}for(int i=1;i<=n;i++)fa[i]=i,hh[i]=1;sort(A+1,A+k+1);sz=unique(A+1,A+k+1)-A-1;sort(q+1,q+k+1,cmp);sort(f+1,f+m+1,cmp1);int j=1,l=1;for(int i=1;i<=sz;i++){ // for(int j=1;j<=n;j++)cout<<fa[j]<<endl;if(l>k)break;for(;j<=m;j++){if(f[j].l>A[i])break;hb(f[j].u,f[j].v);}for(;l<=k;l++){if(q[l].len>A[i])break;ans[q[l].id]=hh[find(q[l].x)];}}for(int i=1;i<=k;i++)printf("%d\n",ans[i]);
}