UVA - 1218 Perfect Service(트리 dp)

제목 링크: UVA - 1218 Perfect Service

제목

n대의 컴퓨터가 있는데 서로 뿌리가 없는 방식으로 연결된다. 현재 그 중 일부 컴퓨터를 서버로 하고 모든 컴퓨터가 반드시 연결되어야 하며 서버(서버로 하는 컴퓨터 제외)만 연결할 수 있도록 요구하며 최소한 몇 대의 컴퓨터를 서버로 해야 하는지를 요구한다.

생각

전형적인 트리 dp 문제, 그러면 우리는 모델을 세웁니다.d(u,0):u는 서버입니다. 아이가 서버인지 아닌지는 모두 d(u,1):u는 서버가 아닙니다. u의 아버지는 서버입니다. u의 아이는 서버가 될 수 없습니다. d(u,2):u는 서버가 아닙니다. u의 아버지는 서버가 아닙니다. u의 아이는 반드시 있어야 하고 하나만이 서버입니다.
그렇다면 명백한 d(u,0)= 1+Sum(Min(d(v,1), d(v,0))｜v는 u의 아이 d(u,1)=Sum(d,2)d(u,2)는 좀 복잡하다. 한 아이만 서버이기 때문에 모든 아이가 서버인 상황을 두루 겪어야 한다. 한 바퀴 한 바퀴는 다른 모든 아이를 동시에 계산해야 하고 O(N^2)의 시간이 필요하다.분명히 이렇게 하면 여러 가지 중복 계산 상황이 있을 것이다. 당연히 기억화하여 속도를 높일 수 있지만, 더 빠른 기교가 하나 있다. 왜냐하면 d(u,1)와 d(u,2)의 유일한 차이점은 d(u,2)의 아이가 서버를 가지고 있기 때문이다. 그러면 우리는 d(u,2)=Min(u,1)-d(v,2)+d(v,0)|v는 u의 아이가 여전히 모든 아이를 서버로 하고 있으며, 매 라운드의 조작은 O(1)로 전체적으로 O(N)이다.

코드

ps: d(u,2)를 처음에 무한대로 설정하기 때문에 0x3f3f3f3f를 설치했는데 결과적으로 N으로 바꾸면 됩니다. 오랫동안 찾아서 문제를 찾았습니다. 이 wrong으로 인해 여러 번 문제가 생겼지만 왜 wrong인지 모르겠습니다. 원인을 아는 도우들은 아낌없는 조언을 해 주십시오.

첫 번째 a의 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

const int N = 10009;
vector<int> g[N];
int dp[N][3];

void dfs(int u, int fa)
{
    for(int i=0; i<g[u].size(); i++)
    {
        if(g[u][i] != fa)
            dfs(g[u][i], u);
    }
    dp[u][0] = 1;
    dp[u][1] = 0;
    dp[u][2] = N;
    for(int i=0; i<g[u].size(); i++)
    {
        if(g[u][i] != fa)
        {
            dp[u][0] += min(dp[g[u][i]][0], dp[g[u][i]][1]);
            dp[u][1] += dp[g[u][i]][2];
        }
    }
    bool f = true;
    for(int i=0; i<g[u].size(); i++)
    {
        if(g[u][i] != fa)
        {
            f = false;
            dp[u][2] = min(dp[u][2], dp[u][1]+dp[g[u][i]][0]-dp[g[u][i]][2]);
        }
    }
}

int main()
{
    int n;
    while(cin>>n)
    {
        memset(dp, -1, sizeof(dp));
        int a, b;
        for(int i=1; i<n; i++)
        {
            cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        dfs(1, -1);
        cout<<min(dp[1][0], dp[1][2])<<endl;

        cin>>a;
        if(a == -1)
            break;
        for(int i=1; i<=n; i++)
            g[i].clear();
    }
    return 0;
}

대신코드를 참관한 후 수정한 간략판

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

const int N = 10009;
vector<int> g[N];
int dp[N][3];

void dfs(int u, int fa)
{
    dp[u][0] = 1;
    dp[u][1] = 0;
    dp[u][2] = N;
    for(int i=0; i<g[u].size(); i++)
    {
        if(g[u][i] != fa)
        {
            dfs(g[u][i], u);
            dp[u][0] += min(dp[g[u][i]][0], dp[g[u][i]][1]);
            dp[u][1] += dp[g[u][i]][2];
        }
    }

    for(int i=0; i<g[u].size(); i++)
    {
        if(g[u][i] != fa)
            dp[u][2] = min(dp[u][2], dp[u][1]+dp[g[u][i]][0]-dp[g[u][i]][2]);
    }
}

int main()
{
    int n;
    while(cin>>n)
    {
        int a, b;
        for(int i=1; i<n; i++)
        {
            cin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        dfs(1, -1);
        cout<<min(dp[1][0], dp[1][2])<<endl;

        cin>>a;
        if(a == -1)
            break;
        for(int i=1; i<=n; i++)
            g[i].clear();
    }
    return 0;
}