【Bzoj1827】【Luogu2986】【Bzoj3743】奶牛大集会

来源和评测点

USACO2010 MAR Gold
Great Cow Gathering
Bzoj1827
Luogu2986

双倍经验:
Coci2015 Kamp
Bzoj3743

题目

【题目大意】
给出n个点,由n-1条边连接ai和bi,长度为li,
形成一棵树,每个点有ci个奶牛。
现在要选一个点,使其他点的奶牛到这里距离×数量之和最小。
【输入格式】
第一行:一个整数N。
第二到N+1行:第i+1行有一个整数Ci
第N+2到2*N行:第i+N+1行有3个整数:Ai,Bi和Li。
【输出格式】
最小的距离×数量之和
【限定条件】
1<=N<=100,000
1<=Ai<=N
1<=Bi<=N
0<=Ci<=1,000
1<=Li<=1,000
【输入样例】
5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3
【输出样例】
15
【样例解释】

刷题记录

30min
忘记开long long,WA了一发

分析

请先思考后再展开

这道题真心水啊,给之前被dp虐惨的我找回一点点信心……
首先一看就是一棵树,那除了树形dp还能是什么~
然后用a表示来自父亲的费用,b表示来自儿子的费用
a还要容斥一下,还好有样例……
$$
a_top=(size[rt]-size[x])\times L_fa
$$

$$
a_brother=b[fa]-b[x]-size[b]\times L_son
$$

$$
a[x]=a[fa]+a_top+a_brother
$$

$$
b[x]=\sum b[son]+size[x]\times L_son
$$

然后就是因为方向不同,所以要dfs两次
复杂度O(2n),这n比较小,主要是这出题人把边搞大了

代码

请先思考后再展开
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
78
79
80
81
82
83
84
85
86
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
ll mymin(ll x,ll y) {return x<y?x:y;}
//*******************全局常量*******************
const int MAXN=110000,MAXM=210000;
const int INF=0x3f3f3f3f;
//*******************全局定义*******************
struct nod
{
int hou;
ll a,b;
ll size;
int fa;
nod()
{
fa=hou=a=b=size=0;
}
}p[MAXN];
struct edge
{
int y,g;
ll c;
}e[MAXM];
int ln=0;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
}
//*******************实现*******************
void dfs1(int x,int fa)//自底向上
{
p[x].fa=fa;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(y==fa) continue;
dfs1(y,x);
p[x].size+=p[y].size;
p[x].b+=p[y].b+p[y].size*e[k].c;
}
}
int n;
ll ans=ll(INF)*ll(INF);
void dfs2(int x)//自上而下
{
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(y==p[x].fa) continue;
ll top=(p[1].size-p[y].size)*e[k].c;
ll brother=p[x].b-p[y].b-p[y].size*e[k].c;
p[y].a=p[x].a+top+brother;
ans=mymin(ans,p[y].a+p[y].b);
dfs2(y);
}
}
//*******************主函数*******************
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&p[i].size);
for(int i=1;i<=n-1;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
dfs1(1,0);
dfs2(1);
ans=mymin(ans,p[1].b);
printf(BIGN,ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4b22.html
转载请注明出处,谢谢!