POJ 3398 Perfect Service(트리 DP)

설명은 n개의 점 n-1변의 컴퓨터 네트워크에서 일부 컴퓨터를 선택하여 서버를 만든다. 서버의 설정에 대해 모든 컴퓨터가 서버이거나 서버와 연결되어야 한다. 그러나 한 컴퓨터가 서버가 아니라면 여러 대의 서버와 연결할 수 없다. 그러나 서버는 서버와 연결될 수 있다. 최소한 몇 대의 서버를 설치해야 하는지 묻는다.각 그룹의 용례 첫 번째 행위는 정수 n으로 포인트를 표시하고 그 다음에 n-1줄은 줄마다 두 개의 정수 a와 b는 a와 b 사이에 가장자리가 있음을 나타낸다. 각 그룹의 용례는 0으로 끝내고 -1로 끝내고 모든 입력 Output은 각 그룹의 용례에 대해출력 최소 설정이 필요한 서버 수 Sample Input 6 1 3 4 5 4 6 0 2 1 2 - 1 Sample Output 2 1 Solution dp[i][0]는 i가 서버이고 i를 루트로 하는 하위 트리가 모두 덮어쓰는 상황에서 서버의 최소 포인트 dp[i][1]는 i가 서버에 속하지 않고 i를 루트로 하는 하위 트리가 덮어쓰는 것을 나타낸다.또한 i가 하위 노드보다 적지 않은 경우 서버의 최소 포인트 dp[i][2]는 i가 서버에 속하지 않고 i를 루트로 하는 하위 트리가 모두 덮어씌워진다는 것을 나타낸다.또한 i가 노드를 덮지 않은 경우 서버의 최소 포인트 dp[i][0]=1+sum(dp[u][0], dp[u][2]) dp[i][1]=INF i에 하위 노드 dp[i][1]=sum(min(dp[u][0], dp[u][1]) +inc i에 하위 노드 inc=0이 있다면sum(dp[u][0], dp[u][1])에 어떤 dp[u][0]가 포함되지 않으면 inc=min(dp[u][0]]]] [2]=sum(dp[u][1]) 결과는min(dp[1][0], dp[1][1]) Code

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 11111
#define INF 0x3f3f3f3f
typedef long long ll;
struct Edge
{
    int to,next;
}edge[2*maxn];
int n,head[maxn],tot;
int dp[maxn][3];
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
    for(int i=0;i<maxn;i++)dp[i][1]=INF;
}
void add(int u,int v)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
void DP(int u,int fa)
{
    dp[u][0]=1,dp[u][2]=0;
    int sum=0,inc=INF,flag=0;
    for(int i=head[u];~i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa)continue;
        DP(v,u);
        dp[u][0]+=min(dp[v][0],dp[v][2]);
        if(dp[v][0]<=dp[v][1])
            sum+=dp[v][0],flag=1;
        else sum+=dp[v][1],inc=min(inc,dp[v][0]-dp[v][1]);
        if(dp[v][1]!=INF&&dp[u][2]!=INF)dp[u][2]+=dp[v][1];
        else dp[u][2]=INF;
    }
    if(inc!=INF&&!flag)dp[u][1]=INF;
    else
    {
        dp[u][1]=sum;
        if(!flag)dp[u][1]+=inc;
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        init();
        int u,v,t;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v),add(v,u);
        }
        DP(1,1);
        int ans=min(dp[1][0],dp[1][1]);
        printf("%d
",ans);
        scanf("%d",&t);
        if(t!=0)break;
    }
    return 0;
}