POJ-1655 Balancing Act 树的重心

题意:完全符合树的重心:即找到一个点,其所有的子树中最大的子树节点最少.

代码如下:

#include <cstdlib> #include <cstring> #include <cstdio> #include <iostream> #include <algorithm> #define MAXN 20000 using namespace std;//说白了这一题就是求一棵树的重心 int N, idx; // 说明有N个节点 //由于节点较多,且数为稀疏图,因此采用邻接表的形式来存储struct Node {int x, next, cnt; // cnt用来说明该边所连接节点为子树的总节点数 bool vis; }e[(MAXN<<1)+5]; // 双向边所致 int head[MAXN+5];void addedge(int a, int b) {++idx;e[idx].vis = false, e[idx].cnt = 0;e[idx].x = b, e[idx].next = head[a];head[a] = idx; }int dfs(int x) { // 得到某条边连接的子树的节点数(入口边不进行计算,否则全为N了)int sum = 0;for (int i = head[x]; i != -1; i = e[i].next) {if (!e[i].vis) { // 如果这条边没有被访问过e[i].vis = e[i^1].vis = true;e[i].cnt += dfs(e[i].x);e[i^1].cnt = N-e[i].cnt;}sum += e[i].cnt;}return sum + 1; }void solve(int &x, int &y) {y = 0x7fffffff;for (int i = 1; i <= N; ++i) {int Max = 0x7fffffff+1;for (int k = head[i]; k != -1; k = e[k].next) {Max = max(Max, e[k].cnt);}if (Max < y) {y = Max;x = i;}} }int main() {int T;scanf("%d", &T);while (T--) {int a, b, x, y;memset(head, 0xff, sizeof (head));idx = -1;scanf("%d", &N);for (int i = 1; i < N; ++i) {scanf("%d %d", &a, &b);addedge(a, b);addedge(b, a);}dfs(1);solve(x, y);printf("%d %d\n", x, y);}return 0; }

 

总结

以上是生活随笔为你收集整理的POJ-1655 Balancing Act 树的重心的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。