The 2018 ACM-ICPC CCPC宁夏 G-Factories（树形dp+背包）

题目：给你n个城市，n-1条道路，每两个城市仅有一条通路，即一个树形结构。让你选择m个叶子节点建立工厂，使得最终任意两个工厂之间距离的累加和最小。

思路：考虑点之间的关系很繁琐，所以我想的是对于一条边来说考虑经过了它多少次。dp[u][i]表示u节点为根的子树上选择了i个叶子节点，会经过u这个子树的边的权值和的最优值。转移方程如下：

dp[u][i]=min( dp[u][i-j]+dp[v][j]+w*j*(m-j) ); v是u的子节点，w是u与v之间边的权值，k*(m-k)表示的是这条边会被经过的次数（j为从v这个树上过来的叶节点数，m-j为其它地方选择的叶节点数）

我特么是智障啊，思路早就想对了，怎么考虑都没错，一直wa，最后才发现结果需要输出 " Case #%d: %lldn " ！！！！！！傻逼错误一直犯，还要注意freopen()！

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e12
const int maxn=1e5+10;
struct node{
int x;
ll w;
node(int _x,ll _w)
{
x=_x;
w=_w;
}
};
vector<node>a[maxn];
int n,t,m,siz[maxn];
ll dp[maxn][102];
void dfs(int u,int fa)
{
if(a[u].size()==1)
{
dp[u][1]=0;
siz[u]=1;///记录叶节点数量
}
dp[u][0]=0;
for(int i=0;i<a[u].size();i++)
{
int v=a[u][i].x;
ll w=a[u][i].w;
if(v==fa) continue;
dfs(v,u);
siz[u]+=siz[v];
dp[u][m]=min(dp[v][m],dp[u][m]);///直接从v上选了m个叶子
for(int j=min(m,siz[u]);j>=1;j--)
{
for(int k=1;k<=min(j,siz[v]);k++)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]+1ll*w*1ll*k*1ll*(m-k));//转移方程
}
}
}
int main()
{
///freopen("in.txt","r",stdin);
scanf("%d",&t);
int cas=0;
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
a[i].clear();
for(int i=1;i<n;i++)
{
int x,y;
ll w;
scanf("%d%d%lld",&x,&y,&w);
a[x].push_back(node(y,w));
a[y].push_back(node(x,w));
}
memset(siz,0,sizeof siz);
int rt=1;
for(int i=1;i<=n;i++)//找到一个不为叶子的节点作为根
if(a[i].size()>1)
{
rt=i;
break;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
dp[i][j]=inf;
for(int i=1;i<=n;i++)
dp[i][0]=0;
dfs(rt,-1);
printf("Case #%d: %lldn",++cas,dp[rt][m]);
}
return 0;
}

最后

以上就是光亮大地为你收集整理的The 2018 ACM-ICPC CCPC宁夏 G-Factories（树形dp+背包）的全部内容，希望文章能够帮你解决The 2018 ACM-ICPC CCPC宁夏 G-Factories（树形dp+背包）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。