[UVA][樹形 DP] 10243 - Fire! Fire!! Fire!!!＠Morris' Blog

2012-06-03 22:08:21| 人氣1,621| 回應0 | 上一篇 | 下一篇

[UVA][樹形 DP] 10243 - Fire! Fire!! Fire!!!

推薦 0 收藏 0 轉貼0 訂閱站台

Problem H
Fire! Fire!! Fire!!!
Input: 
standard input
Output: standard output
Time Limit: 15 
seconds
Memory Limit: 32 MB
 
The ACM 
(Asian 
Cultural 
Museum) authority is planning to install fire 
exits in its galleries in order to handle the emergency situation arising in 
case of a sudden fire. The museum is a collection of numerous interconnected 
galleries. The galleries are connected by corridors in such a way that from any 
gallery there is exactly one path to reach any other gallery without visiting 
any intermediate gallery (a gallery that is on that path) more than once. 
 
However, in order to reduce 
installation cost, it has been decided that not every gallery will have a fire 
exit. Fire exits will be installed in such a way that if any gallery does not 
have a fire exit then at least one of its adjacent galleries must have one and 
for each corridor at least one of the two galleries it connects must have a fire 
exit.. You are hired to determine where to put the fire 
exits under this constraint.
 
However, as a first step, you are 
expected to determine the minimum number of fire exits required.
 
Input
The input file may contain 
multiple test cases. The first line of each test case contains an integer N (1 £ N 
£ 
1,000) indicating the number of galleries in this test case. Then follow N lines where the i-th (1 £ i 
£ 
N) line is the adjacency list of the i-th gallery (Each gallery is 
given a unique identification number from 1 to N for convenience). The adjacency 
list for gallery i starts with an integer ni (0 £ 
ni £ 
N - 1) indicating the 
number of galleries adjacent to this gallery, followed by ni integers giving the 
identification numbers of those galleries.
 
A test case containing a zero for 
N terminates the input. 
 
Output
For each test case in the input 
file print a line containing the minimum number of fire exits required to meet 
the given constraint.
 
Sample 
Input
4
3 2 3 4
1 1
1 
1
1 1
16
4 6 12 15 16
3 3 8 10
4 2 4 6 9
1 3
1 6
3 1 3 
5
1 15
1 2
1 3
1 2
1 16
1 1
1 15
1 15
4 1 7 13 
14
2 1 11
0
 
Sample 
Output
1
6
The galleries are connected by corridors in such a way that from any 
gallery there is exactly one path to reach any other gallery without visiting 
any intermediate gallery (a gallery that is on that path) more than once. 

由於上述的這一句話, 可以得知圖形為樹圖
接著就可以著手 DP 了, 狀態 DP[某點為根的子樹][放置或不放置]
DP[某點為根的子樹][放置] = sigma([子樹][min(放置或不放置)])+1;
DP[某點為根的子樹][不放置] = sigma([子樹][放置]);
特殊處理 n = 1, 選擇放置

#include <stdio.h>
#include <vector>
#define min(x, y) ((x) < (y) ? (x) : (y))
using namespace std;
struct Arc {
    int to;
};
vector<Arc> nd[1001];
int dp[1001][2], used[1001];
void dfs(int node) {
    used[node] = 1;
    dp[node][0] = 0;
    dp[node][1] = 1;
    int i;
    for(vector<Arc>::iterator i = nd[node].begin(); i != nd[node].end(); i++) {
        if(used[i->to] == 0) {
            dfs(i->to);
            dp[node][0] += dp[i->to][1];
            dp[node][1] += min(dp[i->to][0], dp[i->to][1]);
        }
    }
}
int main() {
    int n, i, m, y;
    while(scanf("%d", &n) == 1 && n) {
        for(i = 1; i <= n; i++)
            nd[i].clear(), used[i] = 0;
        Arc tmp;
        for(i = 1; i <= n; i++) {
            scanf("%d", &m);
            while(m--) {
                scanf("%d", &tmp.to);
                nd[i].push_back(tmp);
            }
        }
        dfs(1);
        int ans = min(dp[1][0], dp[1][1]);
        if(n == 1)  ans = 1;
        printf("%d\n", ans);
    }
    return 0;
}

我要檢舉

#10243#Fire! Fire!! Fire!!!

台長： Morris

您可能對以下文章有興趣

[UVA][Negative Weight Cycle] 558 - Wormholes

[UVA] 10488 - Swimming Gopher

[UVA][費式] 10334 - Ray Through Glasses

[UVA] 11888 - Abnormal 89's

人氣(1,621) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[ACM-ICPC][DP] 4867 - Maximum Square
此分類上一篇:[UVA][ST] 12299 - RMQ with Shifts

回應(0)