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 n_i (0 £ n_i £ N - 1) indicating the number of galleries adjacent to this gallery, followed by n_i 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;
}