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 |
大牛帮我看看我的程序为什么超时,是O(n)的啊。#include<stdio.h> #include<algorithm> using namespace std; struct node { int value; node *next; node *tail; }t[100000]; bool mark[100000]; int p[100000],num,n,least; int dfs(int m) { mark[m]=true; int max=0,sum=0; struct node *pt; pt=&t[m]; while(pt->next!=NULL) { pt=pt->next; if(mark[pt->value]) continue; int temp=dfs(pt->value); sum+=temp; max=max>temp?max:temp; } sum++; max=max>n-sum?max:n-sum; if(least==max) p[num++]=m; else if(least>max) { least=max; num=0; p[num++]=m; } return sum; } void add(int m,int value) { node *pt; pt=new node; pt->value=value; pt->next=NULL; t[m].tail->next=pt; t[m].tail=pt; } int main() { scanf("%d",&n); for(int i=0;i<100000;i++) mark[i]=false; num=0; least=100000; for(int i=0;i<100000;i++) t[i].tail=&t[i]; for(int i=0,temp_1,temp_2;i<n-1;i++) { scanf("%d%d",&temp_1,&temp_2); add(temp_1,temp_2); add(temp_2,temp_1); } dfs(1); sort(p,p+num); for(int i=0;i<num;i++) { if(i) printf(" %d",p[i]); else printf("%d",p[i]); } printf("\n"); system("pause"); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator