Strategic Game

Time Limit: 10000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 1054
64-bit integer IO format: %lld ???? Java class name: Main

Prev

Submit Status Statistics Discuss

Next

窗體頂端

Type:

None

?

None Graph Theory ????2-SAT ????Articulation/Bridge/Biconnected Component ????Cycles/Topological Sorting/Strongly Connected Component ????Shortest Path ????????Bellman Ford ????????Dijkstra/Floyd Warshall ????Euler Trail/Circuit ????Heavy-Light Decomposition ????Stable Marriage Problem ????Trees ????Directed Minimum Spanning Tree ????Flow/Matching ????????Graph Matching ????????Bipartite Matching ????????Hopcroft–Karp Bipartite Matching ????????Weighted Bipartite Matching/Hungarian Algorithm ????????Flow ????????Max Flow/Min Cut ????????Min Cost Max Flow ????Minimum Spanning Tree DFS-like ????Backtracking with Pruning/Branch and Bound ????Basic Recursion ????IDA* Search ????Parsing/Grammar ????DFS/BFS ????Advanced Search Techniques ????????Binary Search/Bisection ????????Ternary Search Geometry ????Basic Geometry ????Computational Geometry ????Convex Hull ????Pick's Theorem Game Theory ????Green Hackenbush/Colon Principle/Fusion Principle ????Nim ????Sprague-Grundy Number Matrix ????Gaussian Elimination ????Matrix Exponentiation Data Structures ????Basic Data Structures ????Binary Indexed Tree ????Binary Search Tree ????Hashing ????Orthogonal Range Search ????Range Minimum Query/Lowest Common Ancestor ????Segment Tree/Interval Tree ????Trie Tree ????Sorting ????Disjoint Set ????Dancing link String ????Aho Corasick ????Knuth-Morris-Pratt(KMP) ????Suffix Array/Suffix Tree Math ????Basic Math ????Big Integer Arithmetic ????Number Theory ????????Chinese Remainder Theorem ????????Extended Euclid ????????Inclusion/Exclusion ????????Modular Arithmetic ????Combinatorics ????????Group Theory/Burnside's ????????Counting ????????Probability/Expected Value Others ????Tricky ????Hardest ????Unusual ????Brute Force ????Implementation ????Constructive Algorithms ????Two Pointer ????Bitmask ????Beginner ????Discrete Logarithm/Shank's Baby-step Giant-step Algorithm ????Greedy ????Divide and Conquer Dynamic Programming Tag it!

窗體底端

Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?

Your program should find the minimum number of soldiers that Bob has to put for a given tree.

The input file contains several data sets in text format. Each data set represents a tree with the following description:

the number of nodes
the description of each node in the following format
node_identifier:(number_of_roads) node_identifier1 node_identifier2 ... node_identifier
or
node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.

For example for the tree:



the solution is one soldier ( at the node 1).

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table:

Sample Input

4

0:(1) 1

1:(2) 2 3

2:(0)

3:(0)

5

3:(3) 1 4 2

1:(1) 0

2:(0)

0:(0)

4:(0)

Sample Output

1

2

?

題意：

?????? 給出一棵n個結點的樹，現在需要選擇最少的點，使得所有的邊都具有至少一個被選擇的點，輸出這個最少的點數。

分析：

?????? 由于題目中的結點呈現樹結構，所以可以考慮記憶化搜索。在建圖的時候考慮存儲每個結點子結點的數量。搜索點的順序在樹上是由上至下，dp[pos][0]，表示當前位于pos結點并且不選擇pos結點時這個pos結點對應的子樹最少需要選擇多少個點才能在子樹上滿足題目的條件；dp[pos][1]表示的則是選擇pos這個結點。如果pos這個結點沒有選擇，則它的子結點必須全部都被選擇；如果pos沒有被選擇，則它的子結點可選擇可不選擇。即dp[i][0]=sum(dp[son[i][j]][1]) dp[i][1]=sum(min(dp[son[i][j]][0],dp[son[i][j]][1]))。

1 #include <cstdio> 2 #include <cstring> 3 int min(int a,int b){return a < b ? a : b;} 4 const int MAX_N = 1500; 5 int n; 6 int son[MAX_N + 1][MAX_N + 1],dp[MAX_N + 1][2],son_num[MAX_N + 1],f[MAX_N + 1]; 7 // 位于pos，放或者不放soldier的行為帶來的數量答案 8 int dfs(int pos,int key){ 9 if(dp[pos][key] != -1) return dp[pos][key]; 10 int ans = key; 11 for(int i = 0 ; i < son_num[pos] ; i++) 12 if(key == 0) 13 ans += dfs(son[pos][i],1); // 子結點必須全部選擇放1個soldier 14 else 15 ans += min(dfs(son[pos][i],0),dfs(son[pos][i],1)); 16 return dp[pos][key] = ans; 17 } 18 int main(){ 19 while(scanf("%d",&n) == 1){ 20 memset(dp,-1,sizeof dp); 21 for(int i = 0 ; i < n ; i++) f[i] = i; // 用于尋找根結點 22 for(int i = 0 ; i < n ; i++){ 23 int x,m; scanf("%d:(%d)",&x,&m); 24 son_num[x] = m; 25 for(int j = 0 ; j < m ; j++){ 26 scanf("%d",&son[x][j]); 27 f[son[x][j]] = x; 28 } 29 } 30 int ans = 0; 31 for(int i = 0 ; i < n ; i++)if(f[i] == i) 32 ans = min(dfs(i,1),dfs(i,0)); 33 printf("%d\n",ans); 34 } 35 return 0; 36 } View Code

?

轉載于:https://www.cnblogs.com/cyb123456/p/5917714.html

總結

以上是生活随笔為你收集整理的hdu1054的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。