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