Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

小草版tarjan 282ms

Posted by diwulechao at 2009-07-26 16:22:47 on Problem 1986 and last updated at 2009-07-26 16:23:50
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator