[luoguP1364] 医院设置（树的重心）

传送门

假设数据再大些，我这就是正解，然而题解里总是各种水过。

两边dfs，一遍求重心，一遍统计距离。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #define MAXN 1001 4 5 using namespace std; 6 7 int n, cnt, tot, ans, sum; 8 int head[MAXN], next[MAXN], to[MAXN], val[MAXN], size[MAXN], dis[MAXN], f[MAXN]; 9 10 inline void add(int x, int y) 11 16 17 inline void dfs(int u) 18 30 } 31 if(2 * size[u] >= tot && !ans) ans = u; 32 } 33 34 inline void dfs1(int u) 35 46 } 47 } 48 49 int main() 50 61 dfs(1); 62 dis[ans] = 1; dfs1(ans); 64 printf("%d", sum); 65 return 0; 66 }
View Code

上一篇：清北澡堂七日游

下一篇：树的重心

---

树的重心