Cell Phone Network
Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.
Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.
Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.
Input
* Line 1: A single integer: N
* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B
Output
* Line 1: A single integer indicating the minimum number of towers to install
Sample Input
5
1 3
5 2
4 3
3 5
Sample Output
2
Source
题目类型：最小点支配(树形DP)
算法分析：dp[u][1]表示以u为根的子树在u这个节点上面安排士兵所具有的最小点支配数，dp[u][2]表示以u为根的子树在u这个节点上不安排士兵，而被其子节点所支配的最小点支配数，dp[u][3]表示以u为根的子树在u这个节点上不安排士兵，而被其父节点所支配的最小点支配数。初始条件是dp[u][1] = 1, dp[u][2] = dp[u][3] = 0，状态转移方程为：
dp[u][1] += min (dp[v][1], dp[v][2], dp[v][3])
dp[u][3] += min (dp[v][1], dp[v][2])
(1)dp[u][2] = INF(若u是叶子节点)
(2)dp[u][2] = 若选择了的u所有子节点中有dp[v][1]则计算完后直接返回即可，反之则使用一个变量来记录dp[v][1] - dp[v][2]的最小值，最后循环完之后再加上这个变量的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 6; //分别表示顶点v。w和下一个邻接的位置 struct Node { int v, w, next; }; Node edge[maxn]; int head[maxn], edgelen;//分别表示顶点的表头节点和边的数量 //将所有的数组均初始化为-1 void Init () { memset (head, -1, sizeof (head)); memset (edge, -1, sizeof (edge)); edgelen = 0; } //使用头插法构建 void AddEdge (int u, int v, int w) { edge[edgelen].v = v; edge[edgelen].w = w; edge[edgelen].next = head[u]; head[u] = edgelen++; } bool vis[maxn]; int dp[maxn][6]; void dfs (int rt) { vis[rt] = true; bool is_valid = true; int tt = INF; for (int i = head[rt]; i != -1; i = edge[i].next) { if (!vis[edge[i].v]) { dfs (edge[i].v); dp[rt][1] += min (dp[edge[i].v][1], min (dp[edge[i].v][2], dp[edge[i].v][3])); dp[rt][3] += min (dp[edge[i].v][1], dp[edge[i].v][2]); if (dp[edge[i].v][1] <= dp[edge[i].v][2]) { dp[rt][2] += dp[edge[i].v][1]; is_valid = false; } else { dp[rt][2] += dp[edge[i].v][2]; tt = min (tt, dp[edge[i].v][1] - dp[edge[i].v][2]); } } } if (is_valid) dp[rt][2] += tt; } int main() { // CFF; int n; while (scanf ("%d", &n) != EOF) { Init (); for (int i = 1; i <= n; i++) { int u, v; scanf ("%d%d", &u, &v); AddEdge (u, v, 1); AddEdge (v, u, 1); } memset (vis, false, sizeof (vis)); for (int i = 1; i <= n; i++) dp[i][2] = dp[i][3] = 0, dp[i][1] = 1; dfs (1); printf ("%d\n", min (dp[1][1], dp[1][2])); } return 0; } |
- « 上一篇：poj1463
- poj2385：下一篇 »