首页 > 代码库 > POJ 3107 - Godfather
POJ 3107 - Godfather
本题与POJ 1655的区别是要把所有重心的点按顺序输出出来。
// poj3107 Godfather #include <cstdio> #include <cstring> #define NDEBUG #define MAXN 50005 using namespace std; int N; int edgefw[MAXN*2], edge[MAXN*2], head[MAXN], eptr; #define EI(j, k) ({ \ edge[eptr] = k, edgefw[eptr] = head[j]; head[j] = eptr++; }) int dp[MAXN], dp2[MAXN]; char vis[MAXN]; void dfs(int i) { vis[i] = 1; int p, maxk = 0, sumn = 1; for(p = head[i]; p>=0; p = edgefw[p]) { int t = edge[p]; if (!vis[t]) { if (!dp2[t]) dfs(t); sumn += dp2[t]; if (maxk < dp2[t]) maxk = dp2[t]; } } if (sumn != N && N - sumn > maxk) maxk = N - sumn; dp[i] = maxk, dp2[i] = sumn; } int main(void) { #ifndef NDEBUG freopen("poj3107.in", "r", stdin); #endif // NDEBUG scanf("%d", &N); memset(head, -1, sizeof(int) * N), eptr = 0; int i, j, root; root = 0; for(i=1; i<N; ++i) { int k; scanf("%d%d", &j, &k); --j,--k; EI(j, k), EI(k, j); if (root == k) root = j; } dfs(root); j = 0; for(i = 1; i < N; ++i) if (dp[i] < dp[j]) j = i; root = 0; for(i = 0; i < N; ++i) if (dp[i] == dp[j]) { printf("%d", ++i); break; } for(; i<N; ++i) if (dp[i] == dp[j]) printf(" %d", i+1); putchar(‘\n‘); return 0; }
3107 | Accepted | 4104K | 532MS | G++ | 1249B | 2014-05-01 01:22:57 |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。