树状图怎么画
树状图怎么画如下：
最小树形图，就是给有向带权图中指定一个特殊的点v，求一棵有向生成树T，使得该有向树的根为v，并且T中所有边的总权值最小。
判断是否存在树形图的方法很简单，只需要以v为根作一次图的遍历就可以了，所以下面的算法中不再考虑树形图不存在的情况，在所有操作开始之前，我们需要把图中所有的自环全都清除。
首先为除根之外的每个点选定一条入边，这条入边一定要是所有入边中最小的。所有的最小入边都选择出来了，如果这个入边集不存在有向环的话，我们可以证明这个集合就是该图的最小树形图。
如果存在有向环的话，我们就要将这个有向环所称一个人工顶点，同时改变图中边的权。假设某点u在该环上，并设这个环中指向u的边权是in[u]，那么对于每条从u出发的边(u,i,w)，在新图中连接(new,i,w)的边，其中new为新加的人工顶点;对于每条进入u的边(i,u,w)。
在新图中建立边(i,new,w-in[u])的边。为什么入边的权要减去in[u]，这个后面会解释，在这里先给出算法的步骤。就可以证明，新图中最小树形图的权加上旧图中被收缩的那个环的权和，就是原图中最小树形图的权。
如果新图中e的权w'(e)是原图中e的权w(e)减去in[u]权的话，那么在我们删除掉in[u]，并且将e恢复为原图状态的时候，这个树形图的权仍然是新图树形图的权加环的权，而这个权值正是最小树形图的权值。
这样每次收缩的复杂度是O(E)，然后最多会收缩几次呢?由于我们一开始已经拿掉了所有的自环，我门可以知道每个环至少包含2个点，收缩成1个点之后，总点数减少了至少1。当整个图收缩到只有1个点的时候，最小树形图就不不用求了。
所以我们最多只会进行V-1次的收缩，所以总得复杂度自然是O(VE)了。由此可见，如果一开始不除去自环的话，理论复杂度会和自环的数目有关。
