宁波建站服务,长沙招聘网站有哪些,手工艺品网站建设策划书,湖南天辰建设责任公司网站题目传送门 Description 给你一个矩阵$M$#xff0c;$M(i,j)$表示$i$到$j$的最短距离。定义树的重量为树上各边权之和#xff0c;对于任意给出的合法矩阵$M$#xff0c;已知它所能表示树的重量是唯一确定的。给出一个矩阵#xff0c;求它所表示的树的重量。 Sol 这道题我想…题目传送门 Description 给你一个矩阵$M$$M(i,j)$表示$i$到$j$的最短距离。定义树的重量为树上各边权之和对于任意给出的合法矩阵$M$已知它所能表示树的重量是唯一确定的。给出一个矩阵求它所表示的树的重量。 Sol 这道题我想了一会发现什么思路都没有...然后企图画一点图也无济于事... 后来看题解发现我们其实可以从简单的角度入手逐渐发现规律。 当有两个点的时候显然答案就是$g(1,2)$。 当有三个点的时候如图发生了分叉。因为各点都是叶子节点 图片引用自 TsReaper 设蓝线部分为$len$那么树的重量就是$g(1,2)$$len$。那么$len$部分怎么求稍微想想可以得出$leng(1,3)g(2,3)-g(1,2)$再除以2。 类比一下当有四个...五个...六个...点的时候也会在某一个路径上发生分叉而一个点只可能从在它编号之前的点分叉而来。于是我们对于每个点枚举一下它是从它之前哪个点分叉过来的取个最小值累加即可得到答案。 Code 1 #includecstdio2 #includealgorithm3 #includecstring4 5 using namespace std;6 7 int n,ans;8 int f[50][50];9
10 int main()
11 {
12 while(scanf(%d,n)!EOFn)
13 {
14 for(int i1;in-1;i)
15 for(int ji1;jn;j)
16 scanf(%d,f[i][j]),f[j][i]f[i][j];
17 ansf[1][2];
18 for(int i3;in;i)
19 {
20 int tmp0x3f3f3f3f;
21 for(int j2;ji-1;j)
22 tmpmin(tmp,(f[1][i]-f[1][j]f[i][j])1);
23 anstmp;
24 }
25 printf(%d\n,ans);
26 ans0;
27 memset(f,0,sizeof(f));
28 }
29 return 0;
30 } View Code 转载于:https://www.cnblogs.com/nopartyfoucaodong/p/9781581.html
