首页 > 代码库 > zoj3820 Building Fire Stations 树的中心
zoj3820 Building Fire Stations 树的中心
题意：n个点的树，给出n-1条边，每条边长都是1，两个点建立防火站，使得其他点到防火站的最远距离最短。
思路：比赛的时候和队友一开始想是把这两个点拎起来，使得层数最少，有点像是树的中心，于是就猜测是将树的中心找到后，将两棵左右子树分别求树的中心，这两棵树的中心就是答案，but另外一个队友又说了个反例，脑子也不清醒，以为还有没考虑到的，比赛也没A，赛后一想就是最初的猜想，回来之后写了写，报栈了，数据范围太大，真不想改，今天改了改，改成bfs又tle了，囧囧的，把memset和memcpy都改成循环AC了，代码写的很不优雅。
如果最一开始树的直径是偶数，即1-2-3-4，则拆成1-2和3-4。
如果最一开始树的直径是奇数，即1-2-3-4-5，则拆成1-2-3和3-4-5。
丑丑的代码：
1 /*=============================================================== 2 * Copyright (C) 2014 All rights reserved. 3 * 4 * File Name: zoj3172.cpp 5 * Author:sunshine 6 * Created Time: 2014年10月14日 7 * 8 ================================================================*/ 9 #include <map> 10 #include <queue> 11 #include <math.h> 12 #include <stdio.h> 13 #include <string.h> 14 #include <iostream> 15 #include <algorithm> 16 17 using namespace std; 18 19 #define N 500010 20 21 int head[N]; 22 int edgeNum; 23 struct Edge{ 24 int v,to; 25 }edge[N]; 26 int edge_u_v[N][2]; 27 28 void addedge(int a,int b){ 29 edge[edgeNum].v = b; 30 edge[edgeNum].to = head[a]; 31 head[a] = edgeNum ++; 32 } 33 34 int vis[N],depth,ind; 35 int t_vis[N],father[N]; 36 int stack[N]; 37 void bfs(int u){ 38 vis[u] = 1; 39 queue<int>que; 40 que.push(u); 41 while(!que.empty()){ 42 int tmp = que.front(); 43 que.pop(); 44 if(vis[tmp] >= depth){ 45 depth = vis[tmp]; 46 ind = tmp; 47 } 48 for(int i = head[tmp];i != -1;i = edge[i].to){ 49 int v = edge[i].v; 50 if(vis[v] == 0){ 51 vis[v] = vis[tmp] + 1; 52 father[v] = tmp; 53 que.push(v); 54 } 55 } 56 } 57 int tmp = ind; 58 for(int i = 0;i < depth;i ++){ 59 stack[i] = tmp; 60 tmp = father[tmp]; 61 } 62 return ; 63 } 64 65 66 void init(int n){ 67 edgeNum = 0; 68 //memset(head,-1,sizeof(head)); 69 //memset(vis,0,sizeof(vis)); 70 //memset(father,-1,sizeof(father)); 71 for(int i = 0;i <= n;i ++) { 72 head[i] = -1; 73 vis[i] = 0; 74 father[i] = -1; 75 } 76 } 77 78 int main(){ 79 int t; 80 int n; 81 int u,v; 82 //freopen("data.in","r",stdin); 83 //freopen("data.out","w",stdout); 84 scanf("%d",&t); 85 while(t --){ 86 scanf("%d",&n); 87 88 init(n); 89 for(int i = 0;i < n - 1;i ++){ 90 scanf("%d%d",&u,&v); 91 edge_u_v[i][0] = u; 92 edge_u_v[i][1] = v; 93 addedge(u,v); 94 addedge(v,u); 95 } 96 97 depth = 1; 98 bfs(1); 99 for(int i = 0;i <= n;i ++) vis[i] = 0;100 bfs(ind);101 102 int ans_one,ans_two;103 int depth_one,depth_two;104 //left graph105 init(n);106 u = stack[depth / 2 - 1];//chai bian107 v = stack[depth / 2];108 for(int i = 0;i < n - 1;i ++){109 if((edge_u_v[i][0] == u && edge_u_v[i][1] == v)110 || (edge_u_v[i][1] == u && edge_u_v[i][0] == v)) ;111 else{112 addedge(edge_u_v[i][0],edge_u_v[i][1]);113 addedge(edge_u_v[i][1],edge_u_v[i][0]);114 }115 }116 117 int seperation = stack[depth / 2];//the seperation of left and right118 int seperation1 = stack[(depth - 1) / 2];119 int long_depth = depth;120 depth = 1;121 bfs(seperation);122 for(int i = 0;i <= n;i ++) t_vis[i] = vis[i];123 for(int i = 0;i <= n;i ++) vis[i] = 0;124 bfs(ind);125 ans_one = stack[depth/2];//if depth&1 mid else right126 depth_one = depth;127 128 if(long_depth&1){129 addedge(u,v);130 addedge(v,u);131 t_vis[seperation] = 0;132 }else{133 seperation = seperation1;134 }135 depth = 1;136 for(int i = 0;i <= n;i ++) vis[i] = t_vis[i];137 bfs(seperation);138 for(int i = 0;i <= n;i ++) vis[i] = t_vis[i];139 bfs(ind);140 if(depth & 1) ans_two = stack[depth/2];141 else ans_two = stack[(depth-1)/2];142 depth_two = depth;143 144 if(ans_one == ans_two){145 printf("%d %d %d\n",long_depth/2,ans_one,(ans_one == 1)?2:1);146 }else{147 printf("%d %d %d\n",max(depth_one/2,depth_two/2),ans_one,ans_two);148 }149 150 }151 return 0;152 }
zoj3820 Building Fire Stations 树的中心
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。