网站开发与设计.net,wordpress插图文章排版,网站建设后台程序用什么语言,seo公司发展前景话说宁波市的中小学生在镇海中学参加计算机程序设计比赛#xff0c;比赛之余#xff0c;他们在镇海中学的各个景点参观。镇海中学共有n个景点#xff0c;每个景点均有若干学生正在参 观。这n个景点以自然数1至n编号#xff0c;每两个景点的编号均不同。每两个景点之间有且只…话说宁波市的中小学生在镇海中学参加计算机程序设计比赛比赛之余他们在镇海中学的各个景点参观。镇海中学共有n个景点每个景点均有若干学生正在参 观。这n个景点以自然数1至n编号每两个景点的编号均不同。每两个景点之间有且只有一条路径。选择哪个景点集中所有的学生才能使所有学生走过的路径之和最小呢 输入描述 第一行只有一个正整数n表示景点数。 第二行有n个1至1000间的整数这n个整数间互相以一个空格分隔。其中第i个整数表示第i个景点处的学生数。 第三行至第n1每行有三个整数i,j,k表示景点i和景点j之间有一条长为k的路径直接连接。其中ij1≤i≤n, 1≤j≤n1≤k≤1000。 输出描述 有二行 第一行只有一个整数i表示在第i个景点处集中时所有学生走过的路之和最短。 第二行也只有一个整数表示所有学生走过的路径之和的最小值 1 #includeiostream2 #includecstring3 #includecstdlib4 #includecstdio5 #includecmath6 #includealgorithm7 using namespace std;8 int n,num[100002],a,b,c,g[100002],tot,cnt,poi;//poi为最优点9 long long ans[100002],minn9223372036854775807,siz[100002];//siz[i]以i为根节点的树的点权和minn为最优答案ans[i]为以i为根时的答案
10 struct s1
11 {int t,next;
12 long long l;
13 } e[200002];//e是边的相关信息t是重点next是下一条边l是边权
14 void addedge(int s,int t,int l)//建图
15 {e[tot].nextg[s];
16 g[s]tot;
17 e[tot].tt;
18 e[tot].ll;
19 return;
20 }
21 void geta(int x,int d,int f)//预处理随便找个点这里是1作为根节点遍历整棵树计算以这个点为根时的siz和ans
22 {siz[x]num[x];
23 for(int ig[x];i!0;ie[i].next)
24 if(e[i].t!f)//因为最初是双向建边所以这里应注意不需要重复处理。又因为树上没有环所以别再去找父节点就行
25 {geta(e[i].t,de[i].l,x);
26 siz[x]siz[e[i].t];
27 ans[1]siz[e[i].t]*e[i].l;
28 }
29 return;
30 }
31 void dp(int x,int f)
32 {if(ans[x]minn)//到达每个点时ans必然是已经算好的所以先更新minn和poi
33 {minnans[x];
34 poix;
35 }
36 for(int ig[x];i!0;ie[i].next)//计算好子节点的ans之后再将阶段转移到子节点以继续计算其他的ans
37 if(e[i].t!f)//同样不需要重复处理
38 {ans[e[i].t]ans[x]e[i].l*(cnt-2*siz[e[i].t]);//由ans[e[i].t]ans[x](cnt-siz[e[i].t])*e[i].l-siz[e[i].t]*e[i].l化简而来即以e[i].t为根的子树上的点不需要再经过第i条边其他点需要经过第i条边
39 dp(e[i].t,x);
40 }
41 return;
42 }
43 int main()
44 {freopen(p1487.in,r,stdin);
45 freopen(p1487.out,w,stdout);
46 scanf(%d,n);
47 for(int i1;in;i)
48 {scanf(%d,num[i]);
49 cntnum[i];
50 }
51 for(int i1;in;i)
52 {scanf(%d%d%d,a,b,c);
53 addedge(a,b,c);//注意双向建边
54 addedge(b,a,c);
55 }
56 geta(1,0,0);
57 dp(1,0);
58 coutpoiendlminnendl;
59 return 0;
60 } 转载于:https://www.cnblogs.com/aininot260/p/9681333.html
