洛谷P1395 会议（CODEVS.3029.设置位置）（求树的重心）

题目描述

有一个村庄居住着n个村民，有n-1条路径使得这n个村民的家联通，每条路径的长度都为1。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入输出格式

输入格式：

第一行。一个数n，表示有n个村民。

接下来n-1行，每行两个数字a和b，表示村民a的家和村民b的家之间存在一条路径。

输出格式：

一行输出两个数字x和y

x表示村长将会在哪个村民家中举办会议

y表示距离之和的最小值

输入输出样例

输入样例#1：

输出样例#1：

2 4

说明

【数据范围】

70%数据n<=1000

100%数据n<=50000

思路：

　　求树的重心，然后求重心到每个点的距离。（树的重心百度百科）

　　如果用n遍spfa会超时。

代码：

1.dfs

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=50005,INF=0x3f3f3f3f;
 6 
 7 int n,cnt,Ans,Min,size=INF,H[N<<1],son[N],dep[N];
 8 bool vis[N];
 9 struct Edge
10 {
11     int to,nxt;
12 }e[N<<1];
13 
14 void read(int &now)
15 {
16     now=0;bool f=0;char c=getchar();
17     while(c>'9'||c<'0')
18     {
19         if(c=='-')f=1;
20         c=getchar();
21     }
22     while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar();
23     now= f?-now:now;
24 }
25 
26 void AddEdge(int u,int v)
27 {
28     e[++cnt].to = v;
29     e[cnt].nxt = H[u];
30     H[u] = cnt;
31 }
32 
33 void DFS(int cur)
34 {//求树的重心 
35     vis[cur]=1;
36     son[cur]=0;
37     int tmp=0;
38     for(int i=H[cur];i;i=e[i].nxt)
39     {
40         if(!vis[e[i].to])
41         {
42             DFS(e[i].to);
43             son[cur]+=son[e[i].to]+1;
44             tmp=max(tmp,son[e[i].to]+1);
45         }
46     }
47     tmp=max(tmp,n-son[cur]-1);
48     if(size>tmp || tmp==size&&Ans>cur)
49     {
50         Ans=cur;
51         size=tmp;
52     }
53 }
54 
55 void DFSforDeep(int x,int y,int d)
56 {
57     dep[x]=d;
58     for(int i=H[x];i;i=e[i].nxt)
59       if(y != e[i].to)
60         DFSforDeep(e[i].to,x,d+1);
61 }
62 
63 int main()
64 {
65     read(n);
66     int x,y;
67     for(int i=1;i<n;++i)
68     {
69         read(x);read(y);
70         AddEdge(x,y);
71         AddEdge(y,x);
72     }
73     DFS(1);
74     DFSforDeep(Ans,Ans,0);
75     for(int i=1;i<=n;++i)
76       Min+=abs(dep[Ans]-dep[i]);
77     printf("%d %d",Ans,Min);    
78     return 0;
79 }

2.70分的spfa

 1 #include<queue>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N=50005,INF=0x3f3f3f3f;
 5 
 6 int n,cnt,Ans,Min=INF,H[N<<1],Dist[N];
 7 bool Exist[N];
 8 queue<int>q;
 9 struct Edge
10 {
11     int to,nxt;
12 }e[N<<1];
13 
14 void read(int &now)
15 {
16     now=0;bool f=0;char c=getchar();
17     while(c>'9'||c<'0')
18     {
19         if(c=='-')f=1;
20         c=getchar();
21     }
22     while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar();
23     now= f?-now:now;
24 }
25 
26 void AddEdge(int u,int v)
27 {
28     e[++cnt].to = v;
29     e[cnt].nxt = H[u];
30     H[u] = cnt;
31 }
32 
33 void spfa(int x)
34 {
35     for(int i=1;i<=n;++i)
36       Exist[i]=0,Dist[i]=INF;
37     Dist[x]=0;
38     Exist[x]=1;
39     q.push(x);
40     while(!q.empty())
41     {
42         int cur=q.front();
43         q.pop();
44         Exist[cur]=0;
45         for(int i=H[cur];i;i=e[i].nxt)
46         {
47             int to=e[i].to;
48             if(Dist[to]<=Dist[cur]+1)continue;
49             Dist[to]=Dist[cur]+1;
50             if(!Exist[to])
51               q.push(to),Exist[to]=1;
52         }
53     }
54 }
55 
56 int main()
57 {
58     read(n);
59     int x,y;
60     for(int i=1;i<n;++i)
61     {
62         read(x);read(y);
63         AddEdge(x,y);
64         AddEdge(y,x);
65     }
66     for(int i=1;i<=n;++i)
67     {
68         spfa(i);
69         int sum=0;bool OK=1;
70         for(int j=1;j<=n;++j)
71           if(Dist[j]==INF)
72           {
73                 OK=0;break;//防止累加INF溢出，不知道有没有用 
74           }
75           else
76             sum+=Dist[j];
77         if(sum<Min && OK)
78           Min=sum,Ans=i;
79     }
80     printf("%d %d",Ans,Min);    
81     return 0;
82 }

TLE