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

UVALive - 4015 Caves

編輯:C++入門知識

題意:一棵n個節點的有根樹,樹的邊有正整數權,表示兩個節點之間的距離,你的任務是回答這樣的詢問,從根節點出發,走不超過x單位的距離,最多能走多少個節點,節點經過多次算一個,對於每次的詢問輸出:經過節點數最大的值


思路:樹形DP,因為最近做的樹形DP,都是三維的,最後一維表示是與否的,所以

用d[i][j][c]表示以i為根節點的樹經過了j個節點,1代表不返回i,0返回i,的最短距離

所以我們單獨考慮一棵樹,根節點是i,起先假設它的son[i] = 1,那麼初始話就是d[i][1][0]=d[i][1][1] = 0,接下來就是單獨考慮它的子節點了,首先考慮如果返回的話,就一種可能就是:它走其他的子樹要返回,然後還要對當前的節點要返回;如果不返回的話,那麼它可能走其他的子樹要返回,當前的不返回,還有就是當前的子樹返回,其他的子樹不返回

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 550;

int d[MAXN][MAXN][2];
int n,son[MAXN],cnt[MAXN];
vectorg[MAXN];

void dfs(int x){
    for (int i = 1; i <= n; i++)
        d[x][i][0] = d[x][i][1] = 0x3f3f3f3f;
    d[x][1][0] = d[x][1][1] = 0;
    son[x] = 1;
    for (int i = 0; i < g[x].size(); i += 2){
        int y = g[x][i],len = g[x][i+1];
        dfs(y);
        for (int j = son[x]; j > 0; j--){
            for (int k = 1; k <= son[y]; k++){
                d[x][j+k][1] = min(d[x][j+k][1],d[x][j][1]+d[y][k][1]+len*2);
                d[x][j+k][0] = min(d[x][j+k][0],min(d[x][j][0]+d[y][k][1]+len*2,d[x][j][1]+d[y][k][0]+len));

            }
        }
        son[x] += son[y];
    }
}

int main(){
    int cas = 1;
    while (scanf("%d",&n) != EOF && n){
        for (int i = 0; i <= n; i++)
            g[i].clear();
        memset(cnt,0,sizeof(cnt));
        for (int i = 1; i < n; i++){
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            cnt[u]++;
            g[v].push_back(u);
            g[v].push_back(w);
        }
        int root = 0;
        for (int i = 1; i < n; i++)
            if (!cnt[i])
                root = i;
        dfs(root);
        int q,x;
        scanf("%d",&q);
        printf("Case %d:\n",cas++);
        while (q--){
            scanf("%d",&x);
            int ans = 1; 
            for (int i = 1; i <= n; i++)
                if (d[root][i][0] <= x)
                    ans = i;
            printf("%d\n",ans);
        }
    }
    return 0;
}


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