結果

問題 No.417 チューリップバブル
ユーザー btk
提出日時 2016-08-27 00:37:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 84 ms / 2,000 ms
コード長 1,485 bytes
コンパイル時間 2,145 ms
コンパイル使用メモリ 173,392 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 17:40:16
合計ジャッジ時間 4,363 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

struct I{
    I(){
        ios::sync_with_stdio(false);cin.tie(0);
    }
}init;

typedef vector<int> V;
typedef vector<V> Graph;/*木を構築 Gは木じゃないとだめ*/
/*G:元の隣接リスト P:空の親ノード表 C:空の子ノード隣接リスト*/
void make_tree(int v, Graph &G,Graph &cost, int p, Graph &C,Graph &cc) {
    for (int i=0;i<G[v].size();i++) {
        int e=G[v][i];
        int ccc=cost[v][i];
        if (e != p) {
            C[v].push_back(e);
            cc[v].push_back(ccc);
            make_tree(e, G, cost,v, C,cc);
	}
    }
}

V dfs(int v,Graph& G,Graph &cost,V& U){
    V dp(1001,0);
    dp[0]=U[v];
    for(int id=0;id<G[v].size();id++){
        auto u=G[v][id];
        auto c=cost[v][id];
        auto v=dfs(u,G,cost,U);
        V nxt=dp;
        for(int i=c;i<=1000;i++)
            for(int j=0;i+j<=1000;j++){
                nxt[i+j]=max(nxt[i+j],dp[j]+v[i-c]);
            }
        swap(dp,nxt);
    }
    return dp;
}

int main(){
    int N,M;cin>>N>>M;
    V U(N);
    for(auto &v:U)cin>>v;
    Graph g(N),tree(N),cost(N),cww(N);
    for(int i=1;i<N;i++){
        int A,B,C;
        cin>>A>>B>>C;
        g[A].push_back(B);
        cww[A].push_back(C);
        
        g[B].push_back(A);
        cww[B].push_back(C);
    }
    make_tree(0,g,cww,0,tree,cost);
    V dp=dfs(0,tree,cost,U);
    int res=0;
    for(int i=0;i<=M/2;i++)res=max(res,dp[i]);
    cout<<res<<endl;
    return 0;
}
0