传送门：【POJ】3164 Command Network 题目大意：平面上n个点，分别编号1~n。有m条有向边(u,v)，边权为两点间的笛卡尔距离，表达为(u,v,cost)。现在问你能否选择一些边使得编号为1的点能到达其他所有点并且花费最小。 题目分析：最小树形图入门题。 什么是最小树形图？其实就是有向最小生成树。 那么算法是怎么实现的呢？ 首先，我们从根做一次dfs，判

朱刘算法 参考之 http://blog.csdn.net/wsniyufang/article/details/6747392 http://blog.csdn.net/ac_lion/article/details/8104461 #include<stdio.h>#include<string.h>#include<vector>#include<math.h>

求最小树形图的总权值   即以固定跟为起点 延给定有向边 可以访问所有的点 并所构成的边权值之和最小 求出这个最小总权值 算法步骤： ① 清除自环，输入的时候判断即可 ② 先判断从固定根开始是否可达所有原图中的点。简单搜索加标记位就可以。如果不可就不用说了，肯定没戏。 ③ 为除根之外的每个点选定一条最小入边。 （记pre [vi]为该边的起点） ④ 判断这个入边集是否存在有向环，如果不存

题目来源：POJ 3164 Command Network 题意：求以1为根的最小树形图 没有输出字符串 思路：直接高朱刘算法 不懂的可以百度 学会了就是直接套模板的事情 其实就是不断消圈而已 不构成圈就有解 无法从根到达其他点就无解   #include <cstdio>#include <cstring>#include <cmath>const int maxn = 110;