[USACO10MAR]伟大的奶牛聚集Great Cow Gat…【树形dp】By cellur925

首先这道题是在树上进行的，然后求最小的不方便程度，比较符合dp的性质，那么我们就可以搞一搞树形dp。

设计状态：f[i]表示以i作为聚集地的最小不方便程度。那么我们还需要各点间的距离，但是由于本题数据加强到1e5，开二维数组显然是不现实的，我们可以换一种思路，求d[i]表示其他所有奶牛到 i点的距离和，这样就成功转化过来惹==。

d[u]+=d[v]+size[v]*edge[i].val

然后再预处理size[i]数组表示以i为根的子树上奶牛的数量。这些都是一遍dfs就能搞定的，然后本题其实开始是无根树，这里默认1为根，看做有根树惹==。

转移：我们易知本题的转移是从当前状态转移到未来状态的。冷静分析可得

f[v]=f[u]-size[v]*edge[i].val+(cnt-size[v])*edge[i].val

然后本题中出现几次的转化思想，如上述方程中的cnt在这题中也有体现。

Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 int n,tot;
 8 ll ans=1e40,cnt,size[100090],d[100090],f[100090];
 9 ll val[100090];
10 ll head[100090];
11 struct node{
12     ll to,next,val;
13 }edge[100090*2];
14 
15 ll lmin(ll a,ll b)
16 {
17     if(a<b) return a;
18     else return b;
19 }
20 
21 void add(ll x,ll y,ll z)
22 {
23     edge[++tot].to=y;
24     edge[tot].val=z;
25     edge[tot].next=head[x];
26     head[x]=tot;
27 }
28 
29 void dfs_pre(int u,int fa)
30 {
31     size[u]=val[u];
32     for(ll i=head[u];i;i=edge[i].next)
33     {
34         ll v=edge[i].to;
35         if(v==fa) continue;
36         dfs_pre(v,u);
37         size[u]+=size[v];
38         d[u]+=d[v]+1ll*size[v]*edge[i].val;
39     } 
40 }
41 
42 void TreeDP(int u,int fa)
43 {
44     for(ll i=head[u];i;i=edge[i].next)
45     {
46         ll v=edge[i].to;
47         if(v==fa) continue;
48         f[v]=1ll*f[u]-1ll*size[v]*edge[i].val+1ll*(cnt-size[v])*edge[i].val;
49         ans=lmin(ans,f[v]);
50         TreeDP(v,u);
51     }
52 } 
53 
54 int main()
55 {
56     scanf("%d",&n);
57     for(int i=1;i<=n;i++) scanf("%lld",&val[i]),cnt+=val[i];
58     for(int i=1;i<=n-1;i++)
59     {
60         ll x=0,y=0,z=0;
61         scanf("%lld%lld%lld",&x,&y,&z);
62         add(x,y,z),add(y,x,z);
63     }
64 //    for(int i=1;i<=tot;i++)
65 //        printf("%d %d %lld
",edge[i].to,edge[i].next,edge[i].val);
66 //    return 0;
67     dfs_pre(1,0);
68 //    for(int i=1;i<=n;i++)
69 //        printf("%lld ",d[i]);
70     f[1]=d[1];
71     ans=lmin(ans,f[1]);
72     TreeDP(1,0);
73 //    for(int i=1;i<=n;i++)
74 //        printf("%lld ",f[i]);
75 //    for(int i=1;i<=n;i++)
76 //        ans=lmin(ans,f[i]);
77     printf("%lld",ans);
78     return 0;
79 }

View Code

细节：本题开long long是毋庸置疑的，我开始把ans初值赋成了0x3f3f3f3f,在一般情况下本来够用，但是因为本题数据较大，所以在这种环境下就显得偏小了，可开到1e40.

[USACO10MAR]伟大的奶牛聚集Great Cow Gat…【树形dp】By cellur925

相关推荐