CCF 2019 9月城市规划（树形dp边的贡献）

本文主要是介绍CCF 2019 9月城市规划（树形dp边的贡献），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：
将点之间的距离和转化为边的贡献。
和这个题一模一样。
2018银川邀请赛 G - Factories Gym - 102222G（树形DP）

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
const ll INF = 1e18;
const int maxn = 1e5 + 7;
int head[maxn << 1],nex[maxn << 1],to[maxn << 1],val[maxn << 1],tot;
int deg[maxn],siz[maxn],vis[maxn];
ll f[maxn][105];
int n,k;void add(int x,int y,int z)
{to[++tot] = y;nex[tot] = head[x];val[tot] = z;head[x] = tot;
}void init1()
{tot=0;for(int i = 1;i <= n;i++){deg[i] = siz[i] = head[i] = vis[i] = 0;}for(int i = 1;i <= n;i++){head[i + n] = 0;}
}
void init2()
{for(int i = 1;i <= n;i++){f[i][0] = 0;for(int j = 1;j <= k;j++)f[i][j] = INF;if(vis[i] == 1){f[i][1] = 0;siz[i] = 1;}}
}void DP(int u,int fa)
{for(int i = head[u];i;i = nex[i]){int v = to[i],w = val[i];if(v == fa)continue;DP(v,u);siz[u] += siz[v];for(int i = min(k,siz[u]);i >= 1;i--){for(int j = 1;j <= min(i,siz[v]);j++){f[u][i] = min(f[u][i],f[u][i - j] + f[v][j] + w * (k - j) * j);}}}
}int main()
{int kase = 0;int m;scanf("%d%d%d",&n,&m,&k);init1();for(int i = 1;i <= m;i++){int x;scanf("%d",&x);vis[x] = 1;}for(int i = 1;i < n;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);deg[x]++;deg[y]++;}int rt = 1;init2();DP(rt,0);printf("%lld\n",f[rt][k]);return 0;
}

这篇关于CCF 2019 9月城市规划（树形dp边的贡献）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---