gym102222 G. Factories

题目大意：

给一棵n个点的树，选m个点，这m个点只能在叶子节点上，问着m个点中两两之间到达其余各点的距离和最小值是多少
题解：
任意两点的树上距离和问题应从边的贡献角度考虑。

树形dp
设 f[u][i] 表示以 u 为根的子树中，选了 i 个叶子节点的最优解，状态转移方程为：

f[u][i+j]=min(f[u][i+j],f[u][i]+f[v][j]+w∗j∗(j−m))

其中所加项为子节点和父节点之间的边的贡献

/*

[HAOI2015]树上染色  的弱化版

*/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int T,n,m,cas;

int main(){

    for(scanf("%d",&T);T--;){

        scanf("%d%d",&n,&m);

        vector<vector<pair<int,ll> > >e(n+);

        for(int i=,x,y,z;i<n;i++){

            scanf("%d%d%d",&x,&y,&z);

            e[x].emplace_back(y,z);

            e[y].emplace_back(x,z);

        }

        if(m==){printf("Case #%d: 0\n",++cas);continue;}

        if(n==){printf("Case #%d: %lld\n",++cas,e[][].second);continue;}

        vector<vector<ll> > f(n+,vector<ll>(m+,1e14));vector<int>siz(n+,);

        function<void(int,int)>dfs=[&](int u,int fa)->void{

            bool leaf=;

            f[u][]=;

            for(auto t:e[u]){

                int v=t.first;ll w=t.second;

                if(v==fa) continue;

                leaf=;

                dfs(v,u);

                for(int i=min(siz[u],m);~i;i--){

                    for(int j=min(siz[v],m-i);~j;j--){

                        f[u][i+j]=min(f[u][i+j],f[u][i]+f[v][j]+w*(m-j)*j);

                    }

                }

                siz[u]+=siz[v];

            }

            if(leaf){f[u][]=;siz[u]=;}

        };

        int rt=;

        for(int i=;i<=n;i++) if(e[i].size()>){rt=i;break;}

        dfs(rt,);

        printf("Case #%d: %lld\n",++cas,f[rt][m]);

    }

    return ;

}

第二版

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+;

const int M=N<<;

const int Kn=;

typedef long long ll;

int T,n,k,cas;

int tot,to[M],nxt[M],head[N],ind[N],siz[N];ll val[M];bool vis[N];

ll f[N][Kn];

inline void add(int x,int y,ll z){

    ind[x]++;to[++tot]=y;val[tot]=z;nxt[tot]=head[x];head[x]=tot;

}

void dfs(int u,int fa){

    for(int l=head[u];l;l=nxt[l]){

        int v=to[l];ll w=val[l];

        if(v==fa) continue;

        dfs(v,u);

        siz[u]+=siz[v];

        for(int i=min(siz[u],k);i;i--){

            for(int j=,re=min(siz[v],i);j<=re;j++){

                f[u][i]=min(f[u][i],f[u][i-j]+f[v][j]+w*(k-j)*j);

            }

        }

    }

};

void init_dp(){

    for(int i=;i<=n;i++){

        f[i][]=;

        for(int j=;j<=k;j++) f[i][j]=1e17;

        if(ind[i]==) siz[i]=,f[i][]=;

    }

}

inline void Clear(){

    tot=;

    memset(ind,,sizeof ind);

    memset(siz,,sizeof siz);

    memset(head,,sizeof head);

}

int main(){

    for(scanf("%d",&T);T--;Clear()){

        scanf("%d%d",&n,&k);

        for(int i=,x,y,z;i<n;i++){

            scanf("%d%d%d",&x,&y,&z);

            add(x,y,z);

            add(y,x,z);

        }

        int rt=;

        for(int i=;i<=n;i++) if(ind[i]>){rt=i;break;}

        init_dp();

        dfs(rt,);

        printf("Case #%d: %lld\n",++cas,f[rt][k]);

    }

    return ;

}

巴特西

gym102222 G. Factories

gym102222 G. Factories

题目大意：

第二版

最新文章

热门文章