Charlesss

ACM_生成树

ACM_RMQ(2) ACM_二分(5) ACM_二分图(8) ACM_前缀和(1) ACM_动态规划(18) ACM_干货(6) ACM_并查集(3) ACM_拓扑排序(2) ACM_搜索(24) ACM_最短路(14) ACM_树(1) ACM_树状数组(2) ACM_线段树(3) ACM_覆盖问题(2) ACM_连通图(2) CodeForces(131) 未归档(172) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

全部文章 / ACM_生成树（共8篇）

UVA 10766 Organising the Organisation(生成树计数)

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1707 题意是有n个公司，然后每个公司都会像题中的...

2019-01-09

0 587

HDU 4009 Transfer water(最小树形图+虚根)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4009 题意是在三维地图上有n个村庄，然后要给这n个村庄通水，可以有两个选择，一个是自己打井，花费为村庄的高度乘X，还有就是可以和其他村庄连管道，如果被连接的村庄比连接的村庄低或相等...

2019-01-09

0 570

UVA 11183 Teen Girl Squad(最小树形图模板)

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2124 题意就是一个人xxx要给n-1个人打电话，...

2019-01-08

0 483

POJ 3164 Command Network(最小树形图)

题目链接：http://poj.org/problem?id=3164 题意是有n个点m条边，然后输入n个点的坐标，然后输入m个u,v表示相连的两个点，权值为两点间距离，边为单向边，问能否将n个点连起来，且花费最少。其实就是一个有向图的最小生成树，叫做最小树形...

2019-01-08

0 554

UVA 10462 Is There A Second Way Left?(带重边次小生成树)

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1403 题意是有n个点m条边，输入m条边和它的权值...

2019-01-07

0 633

HDU 4081 (次小生成树变形)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4081 题意是有n个点，分别输入n个点的坐标和这个点的权值，然后要给这些点建边，建边的权值就是两点间的距离，现在可以免费的建一条边，求免费建边的两个点的权值和与总费用的最大值。 ...

2019-01-07

0 777

UVA 10600 ACM Contest and Blackout(次小生成树)

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1541 直接求最小生成树和次小生成树就好了......

2019-01-07

0 511

POJ 1679 The Unique MST(Kruskal+记录边)

题目链接：http://poj.org/problem?id=1679 题意是给了n个点，m条边，问最小生成树是否唯一首先我们求一个最小生成树把每条边记录下来，然后我们对这个最小生成树进行删边操作，再删除一条边后，能不能再生成一个权值相同的最小生成树就行了。我...

2018-12-15

0 481