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

大牛帮帮我:总是TLE,只想到枚举每个点,然后对其DFS,最后还是超时,不知道怎么改:(附代码)

Posted by zhb_msqx at 2007-08-24 20:32:36 on Problem 1655
#include <iostream>
#include <fstream>
using namespace std;
	

int noden;
int graph[3000][3000];

int mark[30000];     //标记是否访问过


int dfs(int k,int exp){   //对k这个节点广度优先遍历。 不要和exp这个点相连接
	int balance=1;
	for(int i=1;i<=noden;i++){
		if(i!=exp&&i!=k&&mark[i]==0&&graph[k][i]==1){
			mark[i]=1;
			balance+=dfs(i,exp);
		}
	}
	return balance;
}

int getbalance(int exp){
	for(int i=0;i<=noden;i++){
		mark[i]=0;
	}
	int balance=0;
	for(i=1;i<=noden;i++){
		int tmp=0;
		if(i!=exp&&mark[i]==0){
			mark[i]=1;
			tmp=dfs(i,exp);
		}
		if(tmp>balance)balance=tmp;
	}
	return balance;
}



void main(){
//	ifstream cin("data.txt");
	int testcase;
	cin>>testcase;
	for(int tc=0;tc<testcase;tc++){
		cin>>noden;
		memset(graph,0,sizeof(graph));
		memset(mark,0,sizeof(mark));

		for(int i=0;i<noden-1;i++){
			int x,y;
			cin>>x>>y;
			graph[x][y]=graph[y][x]=1;
		}
		int balance=10000;
		int delnode=0;
		for(i=1;i<=noden;i++){
			int tmp=getbalance(i);
			if(tmp<balance){
				balance=tmp;
				delnode=i;
			}
		}
		cout<<delnode<<" "<<balance<<endl;
	}
}

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