UVA - 1218 Perfect Service(树形dp)

题目链接：

题意

思路

代码

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;

}