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 |
小草版tarjan 282msIn Reply To:我的TARJAN 要1.2+ 好慢,谁有好的模板? Posted by:longpo at 2009-04-25 03:12:39 //tarjan 282ms #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; struct node{ int u,v,bh,dis; }a[40010]; int du[40010],p[40010],top,bhtop,now; int f(int x) { if(x!=p[x])p[x]=f(p[x]); return p[x]; } struct treenode{ int to,dis; treenode*next; }*list[40010],edge[80010]; struct checknode{ int source,target,ns,nt,ans,ybh; }check[10010]; int newbh[40010],nowdis,dis[40010]; bool op1(checknode x,checknode y){return x.nt<y.nt;} bool op2(checknode x,checknode y){return x.ybh<y.ybh;} void doit(int k,int from) { for (treenode*p=list[k];p;p=p->next) if (p->to!=from) { nowdis+=p->dis; doit(p->to,k); nowdis-=p->dis; } dis[k]=nowdis; newbh[k]=++bhtop; } int m; void doit2(int k,int from) { for (treenode*poi=list[k];poi;poi=poi->next) if (poi->to!=from) { doit2(poi->to,k); p[poi->to]=f(k); // printf("%d %d \n",poi->to,k); } while (now<=m&&check[now].nt==newbh[k]) { int fa=f(check[now].source); check[now].ans=dis[check[now].source]+dis[check[now].target]-dis[fa]-dis[fa]; now++; } } int main() { int n; // freopen("c:\\input.txt","r",stdin); scanf("%d%*d",&n); for (int i=1;i<n;i++) { scanf("%d%d%d%*c%*c",&a[i].u,&a[i].v,&a[i].dis); du[a[i].v]++; du[a[i].u]++; edge[++top].to=a[i].v; edge[top].next=list[a[i].u]; edge[top].dis=a[i].dis; list[a[i].u]=edge+top; edge[++top].to=a[i].u; edge[top].next=list[a[i].v]; edge[top].dis=a[i].dis; list[a[i].v]=edge+top; } scanf("%d",&m); for (int i=1;i<=m;i++) scanf("%d%d",&check[i].source,&check[i].target); int root; for (int i=1;i<=n;i++) if (du[i]==1) {root=i;break;} for (int i=1;i<=n;i++) p[i]=i; doit(root,0); for (int i=1;i<=m;i++) { check[i].ns=newbh[check[i].source]; check[i].nt=newbh[check[i].target]; if (check[i].ns>check[i].nt) { swap(check[i].ns,check[i].nt); swap(check[i].source,check[i].target); } check[i].ybh=i; } sort(check+1,check+m+1,op1); now=1; doit2(root,0); sort(check+1,check+m+1,op2); for (int i=1;i<=m;i++) printf("%d\n",check[i].ans); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator