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

大牛帮我看看我的程序为什么超时,是O(n)的啊。

Posted by lujunda at 2012-04-08 11:46:10 on Problem 3107
#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:
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