POJ 1463 Strategic game 最小點覆蓋集（樹形dp）

點擊打開鏈接 Strategic game Time Limit: 2000MS Memory Limit: 10000K Total Submissions: 6105 Accepted: 2808

Description

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.

For example for the tree:

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

Input

The input 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_identifier₁ node_identifier₂ ... node_identifier_{number_of_roads}
or
node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500);the number_of_roads in each line of input will no more than 10. Every edge appears only once in the input data.

Output

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:

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

Source

Southeastern Europe 2000
給你一顆樹，讓你求最小點覆蓋。 最小點覆蓋：從V中取盡量少的點組成一個集合，使得E中所有邊都與取出來的點相連。 dp[i][0]表示點i屬於點覆蓋，並且以點i為根的子樹中所連接的邊都被覆蓋的情況下點覆蓋集中所包含最少點的個數。 dp[i][1]表示點i不屬於點覆蓋，且以i為根的子樹中所連接的邊都被覆蓋的情況下點覆蓋集中所包含最少點的個數。 對於第一種狀態dp[i][0]，等於每個兒子節點的兩種狀態的最小值之和+1，方程為：dp[i][0]=1+∑(p[u]=i)min(dp[u][0],dp[u][1]). 對於第二種狀態dp[i][1]，要求所有與i連接的邊都被覆蓋，但是i點不屬於點覆蓋，那麼i點所有孩子子節點都必須屬於覆蓋點，即對於點i的第二種狀態與所有子節點的第一種狀態有關，在樹枝上等於所有子節點的第一種狀態的和，方程為：dp[i][1]=∑(p[u]=i)dp[u][0].

//6508K	375MS
#include
#include
#include
#define M 1507
using namespace std;
int head[M],nodes;
int dp[M][M];
struct E
{
    int v,next;
}edge[M*M];
void addedge(int u,int v)
{
    edge[nodes].v=v;edge[nodes].next=head[u];
    head[u]=nodes++;
}
void DP(int u,int p)
{
    dp[u][0]=1;
    dp[u][1]=0;
    int k,v;
    for(k=head[u];k!=-1;k=edge[k].next)
    {
        v=edge[k].v;
        if(v==p)continue;
        DP(v,u);
        dp[u][0]+=min(dp[v][0],dp[v][1]);
        dp[u][1]+=dp[v][0];
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(head,-1,sizeof(head));
        nodes=0;
        int u,k,v;
        for(int i=0;i