[BZOJ1596] [Usaco2008 Jan]电话网络（树形DP || 贪心）

传送门

1.树形DP

#include <cstdio> #include <cstring> #include <iostream> #define N 10001 using namespace std; int n, cnt; int f[N][3], head[N], to[N << 1], next[N << 1]; bool vis[N]; //f[i][0]表示当前子树全选中，且根节点有放 //f[i][1]表示当前子树全选中，但根节点没放 //f[i][2]表示除了根节点以外，子树全选中 inline int read() inline void add(int x, int y) inline void dfs(int u, int fa) else f[u][1] += f[v][1]; f[u][2] += f[v][1]; } } if(!falg) f[u][1] = tmp; } if(!flag) f[u][1] = 23333333; } int main() dfs(1, 0); printf("%d\n", min(f[1][0], f[1][1])); return 0; }

　

2.贪心

如果一个点的孩子节点或父亲节点有放，那么这个点就不用放了，如果这个点的儿子节点都没放，并且这个点和父亲节点也没放，那么就放在父节点上，ans++

#include <cstdio> #include <cstring> #include <iostream> #define N 10001 using namespace std; int n, cnt, ans; int head[N], to[N << 1], next[N << 1]; bool vis[N], f[N]; inline int read() inline void add(int x, int y) inline void dfs(int u, int fa) } if(!flag && !f[u] && !f[fa]) f[fa] = 1, ans++; } int main() dfs(1, 0); printf("%d\n", ans); return 0; }

　　

上一篇：[BZOJ2733] [HNOI2012]永无乡（并查集 + 线段树合并）

下一篇：[BZOJ1578] [Usaco2009 Feb]Stock Market 股票市场（DP）

---

DP 贪心