程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 1292-Strategic game

UVA 1292-Strategic game

編輯:C++入門知識

UVA 1292-Strategic game


題目大意:給出一棵樹,在某個選擇某個結點可以覆蓋和它相連的所有邊,問最少選多少個結點所有邊都被覆蓋。


解題思路:首先將無根樹轉化為有根樹,0為根。
用d[i][0]表示不選擇結點i時覆蓋以結點i為根的子樹最少要多少個結點,用d[i][1]表示選擇結點i時覆蓋以結點i為根的子樹最少要多少個結點。若結點i不選,為了和覆蓋所有和結點i相連的結點,則每個兒子都必須選,若結點i選,則每個兒子選擇較小的那個值。按DFS順序遞推。
狀態轉移方程:

d[i][0]=sum { d[u][1] }(u是i的兒子)
d[i][1]=sum { min { d[u][0],d[u][1] } }+1(u是i的兒子)
 

#include 
#include 
#include 
using namespace std;

vector  node[1550];
int n, DP[1550][2], vis[1550];

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

    int x, y, num;
    for (int i = 0; i < n; i++) {
        scanf("%d:(%d)", &x, &num);
        for (int j = 0; j < num; j++) {
            scanf("%d", &y);
            node[x].push_back(y);
            node[y].push_back(x);
        }
    }
}

void DPS(int root) {
    vis[root] = 1;
    int num = node[root].size();
    for (int i = 0 ; i < num; i++) {
        int child = node[root][i];
        if (vis[child])
            continue;
        DPS(child);
        DP[root][0] += DP[child][1];
        DP[root][1] += min(DP[child][0], DP[child][1]);
    }
    DP[root][1]++;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        init();
        DPS(0);
        printf("%d\n", min(DP[0][0], DP[0][1]));
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved