程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA - 1220 Party at Hali-Bula

UVA - 1220 Party at Hali-Bula

編輯：C++入門知識

UVA - 1220 Party at Hali-Bula

題目大意：n 個人形成一個關系樹，每個節點代表一個人，節點的根表示這個人的唯一的直接上司，只有根沒有上司。要求選取一部分人出來，使得每 2 個人之間不能有直接的上下級的關系，
求最多能選多少個人出來，並且求出獲得最大人數的選人方案是否唯一。

解題思路：分析發現是要求一個樹的最大獨立集。這裡可以用樹形 DP 解決。

定義dp【x】【0】：表示在 i 點不選 i 點的以 x 為子樹的最大獨立集而dp【x】【1】表示x到場的最大獨立集

定義f 【x】【0】：表示以x為根且x點不選的子樹是否唯一，f【x】【1】表示以x為根且x選的子樹是否唯一

狀態轉移方程：dp [ x ] [ 1 ] + = dp [ child ] [ 0 ] ;

dp [ x ] [ 0 ] + = max ( dp [ child ] [ 0 ] , dp [ child ] [ 1 ] );

而判斷唯一性的方程一樣的。

#include 
#include 
#include 
#include 
#include
using namespace std;

string x, y;
map  vis;
vector  A[210];
int n, DP[210][2], flag[210][2];

void init() {
    for (int i = 0; i <= n; i++) {
        DP[i][0] = DP[i][1] = 0;
        flag[i][0] = flag[i][1] = 1;
        A[i].clear();
    }
    vis.clear();

    int top = 1;
    cin >> x;
    vis[x] = top++;
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        if (!vis[x])
            vis[x] = top++;
        if (!vis[y])
            vis[y] = top++;

        A[vis[y]].push_back(vis[x]);
    }
}

void DPS(int root) {
    int num = A[root].size();
    for (int i = 0; i < num; i++) {
        int child = A[root][i];
        DPS(child);
        DP[root][1] += DP[child][0];
        DP[root][0] += max(DP[child][0], DP[child][1]);
        if (DP[child][0] > DP[child][1] && !flag[child][0] || DP[child][0] < DP[child][1] && !flag[child][1] || DP[child][0] == DP[child][1])
            flag[root][0] = 0;
        if (!flag[child][0])
            flag[root][1] = 0; 
    }
    DP[root][1]++;
}

int main() {
    while (scanf("%d", &n), n) {
        init();
        DPS(1);
        printf("%d ", max(DP[1][0], DP[1][1]));
        if (DP[1][0] > DP[1][1] && flag[1][0])
            puts("Yes");
        else if (DP[1][1] > DP[1][0] && flag[1][1])
            puts("Yes");
        else 
            puts("No");
    }
    return 0;
}