| ||||||||||
| 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,只想到枚举每个点,然后对其DFS,最后还是超时,不知道怎么改:(附代码)#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator