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 |
为毛我的链表也跪了 TLE#include<cstdio> #include<algorithm> #include<cstdlib> #include<ctime> using namespace std; struct point{ int n; point* next; void init(int nn){ n=nn; next=NULL; } }*p; struct link{ point *head,*last; void init(){ head=new point; head->init(0); last=head; } void push(point *p){ last->next=p; last=p; } }l[50010]; int n,s,t,b[50010],son[50010],i,mn=2147483647; bool vd[50010]; void DFS(int x){ vd[x]=true; son[x]=0; b[x]=0; int u; point *p=l[x].head->next; while (p){ u=p->n; if (vd[u]) { p=p->next; continue; } DFS(u); son[x]+=son[u]+1; b[x]=max(b[x],son[u]+1); p=p->next; } b[x]=max(b[x],n-son[x]-1); mn=min(mn,b[x]); } int main(){ srand(time(0)); scanf("%d",&n); for(i=1;i<=n;i++) l[i].init(); for(i=1;i<n;i++) { scanf("%d%d",&s,&t); p=new point; p->init(t); l[s].push(p); p=new point; p->init(s); l[t].push(p); } DFS(rand()%n+1); for(i=1;i<=n;i++) if (mn==b[i]){ printf("%d ",i); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator