题目:给你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()!
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77#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内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复