| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
AC code#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005,M=100005;
int n,m,t,u,v,w,cnt,tot,head[N],nxt[2*N],to[2*N],d[2*N],fa[N],dep[N],siz[N],son[N],pos[N],top[N],maxv[N*4];
bool flag=false;
struct edge
{
int u,v,dis,od;
bool use;
}e[M];
void adde(int u,int v,int w)
{
to[++cnt]=v;
nxt[cnt]=head[u];
d[cnt]=w;
head[u]=cnt;
}
bool cmp(edge a,edge b)
{
return a.dis<b.dis;
}
bool cmp2(edge a,edge b)
{
return a.od<b.od;
}
int find(int u)
{
return u==fa[u]?u:fa[u]=find(fa[u]);
}
void init()
{
cnt=tot=0;
memset(son,-1,sizeof(son));
memset(maxv,0,sizeof(maxv));
memset(head,0,sizeof(head));
for(int i=1;i<=n;i++)
{
fa[i]=i;
e[i].use=false;
}
}
void dfs1(int pre,int u,int d)
{
fa[u]=pre;
dep[u]=d;
siz[u]=1;
for(int v=head[u];v;v=nxt[v])
if(to[v]^fa[u])
{
dfs1(u,to[v],d+1);
if(son[u]==-1||siz[to[v]]>siz[son[u]])
son[u]=to[v];
siz[u]+=siz[to[v]];
}
}
void dfs2(int u,int tp)
{
top[u]=tp;
pos[u]=++tot;
if(son[u]==-1) return;
dfs2(son[u],tp);
for(int v=head[u];v;v=nxt[v])
if(to[v]^fa[u]&&to[v]^son[u])
dfs2(to[v],to[v]);
}
void update(int o,int x,int l,int r,int k)
{
if(l==r)
{
maxv[o]=x;
return;
}
int mid=(l+r)/2;
if(k<=mid) update(o*2,x,l,mid,k);
else update(o*2+1,x,mid+1,r,k);
maxv[o]=max(maxv[o*2],maxv[o*2+1]);
}
int query(int o,int l,int r,int L,int R)
{
if(L<=l&&R>=r) return maxv[o];
int mid=(l+r)/2,ans=0;
if(L<=mid) ans=max(ans,query(o*2,l,mid,L,R));
if(R>mid) ans=max(ans,query(o*2+1,mid+1,r,L,R));
return ans;
}
int Query(int u,int v)
{
int f1=top[u],f2=top[v],ans=0;
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(f1,f2);
swap(u,v);
}
ans=max(ans,query(1,1,n,pos[f1],pos[u]));
u=fa[f1];
f1=top[u];
}
if(u==v) return ans;
if(dep[u]>dep[v]) swap(u,v);
return max(ans,query(1,1,n,pos[son[u]],pos[v]));
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&t))
{
init();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
e[i].u=u;
e[i].v=v;
e[i].dis=w;
e[i].od=i;
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
{
u=find(e[i].u),v=find(e[i].v);
if(u!=v)
{
fa[v]=u;
adde(e[i].u,e[i].v,w);
adde(e[i].v,e[i].u,w);
tot++;
e[i].use=true;
if(tot==n-1)
{
flag=true;
break;
}
}
}
sort(e+1,e+m+1,cmp2);
memset(fa,0,sizeof(fa));
tot=0;
dfs1(0,1,0);
dfs2(1,1);
for(int i=1;i<=m;i++)
if(e[i].use)
{
if(dep[e[i].u]<dep[e[i].v])
swap(e[i].u,e[i].v);
update(1,e[i].dis,1,n,pos[e[i].u]);
}
for(int i=1;i<=t;i++)
{
scanf("%d%d",&u,&v);
puts(Query(e[u].u,e[u].v)>=v?"Yes":"No");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator