首页 > 代码库 > ZOJ 3820:Building Fire Stations(树的直径 Grade C)
ZOJ 3820:Building Fire Stations(树的直径 Grade C)
题意：
n个点的树，边长全为1，求找出两个点，使得树上离这两个点距离最远的那个点，到这两个点（中某个点就行）的距离最小。
思路：
求树直径，找中点，删除中间那条边（如果直径上点数为奇数，则删任何一侧都可），分成两个子树，再求中心，即为答案。
代码：
//14:12#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 200100struct Graph{ struct Edge{ int to; int next; }e[N*3]; int head[N]; int p; void clear() { p = 0; memset(head, -1, sizeof(head)); } void addedge(int u, int v) { e[p].to = v; e[p].next = head[u]; head[u] = p++; }}g;int n;int dis[N];int que[N*10];bool vis[N];int fa[N];void generateDis(const Graph &g, int s) { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); memset(fa, -1, sizeof(fa)); dis[s] = 0; int hd = 0; int tl = 0; que[tl++] = s; vis[s] = 1; while (hd < tl) { int now = que[hd++]; vis[now] = 0; for (int i = g.head[now]; i != -1; i = g.e[i].next) { int to = g.e[i].to; if (dis[to] > dis[now]+1) { dis[to] = dis[now]+1; if (!vis[to]) { vis[to] = 1; fa[to] = now; que[tl++] = to; } } } }}pair<int, int> getTreeMidPoint(const Graph &g, int s, int &OUT_dis) { generateDis(g, s); for (int i = 1; i <= n; i++) { if (dis[i] == 0x3f3f3f3f) dis[i] = -1; } int u = max_element(&dis[1], &dis[1]+n) - dis; generateDis(g, u); for (int i = 1; i <= n; i++) { if (dis[i] == 0x3f3f3f3f) dis[i] = -1; } int v = max_element(&dis[1], &dis[1]+n) - dis; //printf("u = %d, v = %d, dis[v] = %d\n", u, v, dis[v]); int now = v; while (dis[now] > (dis[v]+1)/2) { now = fa[now]; } OUT_dis = dis[v]/2 + dis[v]%2; return {fa[now], now};}int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); g.clear(); for (int i = 0; i < n-1; i++) { int a, b; scanf("%d%d", &a, &b); g.addedge(a,b); g.addedge(b,a); } int tmpdis[2]; pair<int ,int> point = getTreeMidPoint(g, 1, tmpdis[0]); //printf("all tree get (%d %d, dis=%d)\n", point.first, point.second, tmpdis[0]); for (int i = g.head[point.first]; i != -1; i=g.e[i].next) { if (g.e[i].to == point.second) g.e[i].to = point.first; } for (int i = g.head[point.second]; i != -1; i=g.e[i].next) { if (g.e[i].to == point.first) g.e[i].to = point.second; } pair<int ,int> pa = getTreeMidPoint(g, point.first, tmpdis[0]); pair<int ,int> pb = getTreeMidPoint(g, point.second, tmpdis[1]); printf("%d %d %d\n", max(tmpdis[0], tmpdis[1]), pa.second, pb.second); } return 0;}
ZOJ 3820:Building Fire Stations(树的直径 Grade C)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。