首页 > 代码库 > 百练3383:Cell Phone Network
百练3383:Cell Phone Network
传送门:http://bailian.openjudge.cn/practice/3383/
【题解】
题目就是最小支配集。
学习了最小支配集的解法:
树形dp(有空可以推一推)
贪心:DFS遍历后逆DFS序进行处理,如果当前这个点不在支配集而且没和支配集连边,那么标记它父亲为支配集成员并处理父亲的父亲和自己(标为和支配集连边的)
具体实现用一个数组记录支配集一个数组记录是否是支配集 or 连过边。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static /* 首先选择一点为树根,再按照深度优先遍历得到遍历序列,按照所得序列 的反向序列的顺序进行贪心,对于一个即不属于支配集也不与支配集中的 点相连的点来说,如果他的父节点不属于支配集,将其父节点加入到支配集 */ int n; int head[M], nxt[M], to[M], tot=0; bool s[M], is[M]; // have been covered yet(in set or connected with ... in set), in set inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } inline void adde(int u, int v) { add(u, v), add(v, u); } int dfn[M], DFN=0, fa[M]; inline void dfs(int x, int fat) { ++DFN; fa[x] = fat; dfn[DFN] = x; for (int i=head[x]; i; i=nxt[i]) if(to[i] != fat) dfs(to[i], x); } int main() { while(cin >> n) { memset(head, 0, sizeof head); tot = 0; DFN = 0; memset(s, 0, sizeof s); memset(is, 0, sizeof is); memset(fa, 0, sizeof fa); for (int i=1, u, v; i<n; ++i) { scanf("%d%d", &u, &v); adde(u, v); } dfs(1, 1); for (int i=n; i>=1; --i) { int x = dfn[i]; if(!s[x]) { if(!is[fa[x]]) is[fa[x]] = 1; s[x] = 1; s[fa[x]] = 1; s[fa[fa[x]]] = 1; } } int ans = 0; for (int i=1; i<=n; ++i) ans += is[i]; if(n == 1) puts("1"); else printf("%d\n", ans); } return 0; }
百练3383:Cell Phone Network
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。