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