其一
概述
最小树形图, 简而言之就是求有向带权图的最小生成树.
官方定义是这样的: 最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。
复制代码通解最小树形图的一种算法是是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法：朱、刘算法。
今天我们就来浅谈一下最小树形图的问题。
最小树形图, 简而言之就是求有向带权图的最小生成树.
官方定义是这样的: 最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。
朱刘算法
大题上完整的朱、刘算法是由四个大步骤组成的：
1、求最短弧集合E
2、判断集合E中有没有有向环，如果有转步骤3，否则转4
3、收缩点，把有向环收缩成一个点，并且对图重新构建，包括边权值的改变和点的处理，之后再转步骤1。
4、展开收缩点，求得最小树形图。
Tips: 算法详解见后
因为我们ACM一般情况下都是在考察队最小树型图的权值问题，所以一般省略步骤4，对于其环的权值和在中间处理过程中就可以处理完毕。所以我们这里就不多讨论步骤4了。
算法详解
1、首先我们先求最短弧集合E，对于当前图如果有n个点（一个有向环的收缩点算作一个点），我们就要选出n-1个点，确定其入边的最短边，由其组成的一个集合我们就叫做最短弧集合E，如果我们枚举到某一个点的时候，它没有入边，那么说明不存在最小树形图，所以这个时候算法结束，回到主函数。
for(int i = 1; i <= n; i++)
if(i != u && !flag[i]) { //u为根节点，flag[i]为1表示该点在某个有向环中且不是该有向环的代表点(缩点)
w[i][i] = INF, pre[i] = i; //初始化当前点的前驱点为自己
for(int j = 1; j <= n; j++)//枚举i的前驱点(从j到i的点),并且求其最短边,加入集合E中
if(!flag[j] && w[j][i] < w[pre[i]][i]) {
pre[i] = j; //更新当前点的前驱点为j
}
//如果当前枚举到的点i没有入边，那么就不存在最小树形图(说明存在图不连通)
if(pre[i] == i)
return -1;
复制代码2、然后我们对集合E中的边进行判断，判断是否有有向环。刚刚的代码实现里边有一个前驱节点的存储，所以在这个部分，我们直接一直向前枚举前驱点即可，如果枚举的前驱点最终能够枚举到根节点，那么这一部分就不存在有向环，否则就存在，对于每一个点都进行向前枚举即可。
int i;
for(i = 1; i <= n; i++) {
if(i != u && !flag[i]) {
int j = i, cnt = 0;
while(j != u && pre[j] != i && cnt <= n)
j = pre[j], ++cnt; //对于每个节点都找前驱节点,看看能否成环
if(j == u || cnt > n)
continue; //最终能回到根或是走过的点超过n个, 说明没有有向环
break; //否则说明存在有向环
}
}
复制代码3、如果存在有向环，我们需要对有向环进行缩点，既然我们是枚举到节点i的时候发现有有向环，我们不妨把有向环里边的点都收缩成点i。对于收缩完之后会形成一个新的图，图的变化规律是这样的：
上图变换成语言描述：如果点u在环内，如果点k在环外，并且从k到u有一条边map[k][u]=w，并且在环内还有一点v，使得map[v][u]=w2，辣么map[k][i]=w-w2；
基于贪心思想，对于环的收缩点i和另外一点k（也在环内），对于环外一点j，如果map[k][j] <map[i][j]，辣么map[i][j]=map[k][j] ，因为是有向图，入收缩点的边要这样处理，出收缩点的边也要这样处理，对于刚刚三个步骤：收缩点，收缩点处理新图的边权值，以及基于贪心思想的最终处理点i的出边入边权值，后两者我们可以合并成一个操作，其分别的代码实现：
int j = i;
memset(vis, 0, sizeof(vis));
do {
//标记环内的点,并且直接对环的权值进行加和记录,在最后找到最小树形图之后就不用展开收缩点了
ans += w[pre[j]][j], j = pre[j], vis[j] = flag[j] = true;
} while(j != i);
flag[i] = false; //环缩成了点i，点i仍然存在
复制代码Tips: 收缩方案不是唯一的
4、处理收缩点后形成的图：
for(int k = 1; k <= n; ++k)
if(vis[k]) { //在环中的点,在收缩点的时候已经把在环中的点标记了。
for(int j = 1; j <= n; j++)
if(!vis[j]) { // 不在环中的点
if(w[i][j] > w[k][j])
w[i][j] = w[k][j];
if(w[j][k] < INF && w[j][k] - w[pre[k]][k] < w[j][i])
w[j][i] = w[j][k] - w[pre[k]][k];
}
}
复制代码处理完4之后，我们就回到步骤1，继续找最小弧集E，最后找到了一个没有环的最小弧集E之后，对于没有弧的集合E中的所有边（包括能将收缩点展开的边）就是我们要求的最小树形图的边集。
因为我们ACM一般求的都是最小树形图的权值，所以我们一般不需要展开收缩点，在处理环的时候，直接将其边权值记录下来就好，当找到一个没有环的集合E的时候，对其中的最后边权值进行加和即可，对于最后这部分的加权，代码实现:
if(i > n) {
//这块代码是紧接着代码2之后的部分,如果枚举了所有点都没有发现有向环,就说明找到了最终集合。
for(int i = 1; i <= n; i++)
if(i != u && !flag[i])
ans += w[pre[i]][i]; //最后对这个最后的集合E里边所有边加和即可。
return ans;
}
复制代码完整的朱、刘算法代码实现（没有展开收缩点的, 邻接矩阵版）：
bool vis[maxn], flag[maxn];
int pre[maxn];
void init() { //初始化
memset(vis, 0, sizeof(vis));
memset(flag, 0, sizeof(flag));
fill(w[0], w[0] + maxn * maxn, inf);
}
double directed_mst(int u) { //u为根节点
double ans = 0;
memset(vis, 0, sizeof(vis));
while(true) {
//求最短弧集合E
for(int i = 1; i <= n; i++)
if(i != u && !flag[i]) {
w[i][i] = INF, pre[i] = i;
for(int j = 1; j <= n; j++)
if(!flag[j] && w[j][i] < w[pre[i]][i]) {
pre[i] = j;
}
if(pre[i] == i)
return -1;//也可以用dfs预处理判断凸的连通
}
//判断E是否有环
int i;
for(i = 1; i <= n; i++) {
if(i != u && !flag[i]) {
int j = i, cnt = 0;
while(j != u && pre[j] != i && cnt <= n)
j = pre[j], ++cnt;
if(j == u || cnt > n)
continue; //最终能回到根或是走过的点超过n个, 说明没有有向环
break;
}
}
if(i > n) {
for(int i = 1; i <= n; i++)
if(i != u && !flag[i])
ans += w[pre[i]][i];
return ans;
}
//有环,进行收缩,把整个环都收缩到一个点i上。
int j = i;
memset(vis, 0, sizeof(vis));
do {
//标记环内的点,并且直接对环的权值进行加和记录,在最后找到最小树形图之后就不用展开收缩点了
ans += w[pre[j]][j], j = pre[j], vis[j] = flag[j] = true;
} while(j != i);
flag[i] = false; //环缩成了点i，点i仍然存在
//收缩点的同时，对边权值进行改变
for(int k = 1; k <= n; ++k)
if(vis[k]) { //在环中的点
for(int j = 1; j <= n; j++)
if(!vis[j]) { // 不在环中的点
if(w[i][j] > w[k][j])
w[i][j] = w[k][j];
if(w[j][k] < INF && w[j][k] - w[pre[k]][k] < w[j][i])
w[j][i] = w[j][k] - w[pre[k]][k];
}
}
}
return ans;
}
复制代码Tips: 不推荐使用邻接矩阵, 会超时
//使用kuangbin的板子改成从0开始, 点值--.
复制代码参考 : www.cnblogs.com/xzxl/p/7243…
其二
一、相关定义
定义：设G = (V,E)是一个有向图，它具有下述性质：
1. G中不包含有向环；
2. 存在一个顶点vi，它不是任何弧的终点，而V中的其它顶点都恰好是唯一的一条弧的终点，则称 G是以vi为根的树形图。
最小树形图就是有向图G = (V, E)中以vi为根的树形图中权值和最小的那一个。
另一种说法：最小树形图，就是给有向带权图一个特殊的点root，求一棵以root为根节点的树使得该树的的总权值最小。
性质：最小树形图基于贪心和缩点的思想。
缩点：将几个点看成一个点，所有连到这几个点的边都视为连到收缩点,所有从这几个点连出的边都视为从收缩点连出
二、算法描述
【概述】
为了求一个图的最小树形图，①先求出最短弧集合E0；②如果E0不存在，则图的最小树形图也不存在；③如果E0存在且不具有环，则E0就是最小树形图；④如果E0存在但是存在有向环，则把这个环收缩成一个点u，形成新的图G1，然后对G1继续求其的最小树形图，直到求到图Gi，如果Gi不具有最小树形图，那么此图不存在最小树形图，如果Gi存在最小树形图，那么逐层展开，就得到了原图的最小树形图。
【实现细节】
设根结点为v0，
○ （1）求最短弧集合E0
从所有以vi(i ≠ 0)为终点的弧中取一条最短的，若对于点i，没有入边，则不存在最小树形图，算法结束；如果能取，则得到由n个点和n-1条边组成的图G的一个子图G’，这个子图的权值一定是最
小的，但是不一定是一棵树。
○ （2）检查E0
若E0没有有向环且不包含收缩点,则计算结束，E0就是图G以v0为根的最小树形图；若E0含有有向
环，则转入步骤(3)；若E0没有有向环,但是存在收缩点，转到步骤(4)。
○ （3）收缩G中的有向环
把G中的环C收缩成点u，对于图G中两端都属于C的边就会被收缩掉，其他弧仍然保留，得到一个新的图G1，G1中以收缩点为终点的弧的长度要变化。变化的规则是：设点v在环C中，且环中指向v的边的权值为w，点v’不在环C中，则对于G中的每一条边<v’, v>，在G1中有边<v’, u>和其对应，且权值WG1(<v’, u>) = WG(<v’, v>) – w；对于图G中以环C中的点为起点的边<v’, v>，在图G1中有边<u, v’>，则WG1(<u, v’>) = WG(<v’, v>)。有一点需要注意,在这里生成的图G1可能存在重边。
对于图G和G1：
①如果图G1中没有以v0为根的最小树形图，则图G也没有；
②如果G1中有一v0为根的最小树形图，则可按照步骤（4）的展开方法得到图G的最小树形图。
所以，应该对于图G1代到(1)中反复求其最小树形图，直到G1的最小树形图u求出。
○ （4）展开收缩点
假设图G1的最小树形图为T1,那么T1中所有的弧都属于图G的最小树形图T。将G1的一个收缩点u展
开成环C，从C中去掉与T1具有相同终点的弧，其他弧都属于T。
【小结】
对最小树形图做个小小的总结：
1：清除自环，自环是不可能存在于任何最小树形图中的；
2：求出每个顶点的的最小入边；
3：判断该图是否存在最小树形图，由 1 可以判定，或者以图中顶点v作为根节点遍历该图就能判
断是否存在最小树形图；
4：找环，之后建立新图，缩点后重新标记。
struct node { //边的权和顶点
int u, v;
type w;
} edge[MAXN * MAXN];
int pre[MAXN], id[MAXN], vis[MAXN], n, m;
type in[MAXN];//存最小入边权,pre[v]为该边的起点
type Directed_MST(int root, int V, int E) {
type ret = 0;//存最小树形图总权值
while(true) {
int i;
//1.找每个节点的最小入边
for( i = 0; i < V; i++)
in[i] = INF;//初始化为无穷大
for( i = 0; i < E; i++) { //遍历每条边
int u = edge[i].u;
int v = edge[i].v;
if(edge[i].w < in[v] && u != v) { //说明顶点v有条权值较小的入边 记录之
pre[v] = u;//节点u指向v
in[v] = edge[i].w;//最小入边
}
}
for( i = 0; i < V; i++) { //判断是否存在最小树形图
if(i == root)
continue;
if(in[i] == INF)
return -1;//除了根以外有点没有入边,则根无法到达它 说明它是独立的点 一定不能构成树形图
}
//2.找环
int cnt = 0;//记录环数
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
in[root] = 0;
for( i = 0; i < V; i++) { //标记每个环
ret += in[i];//记录权值
int v = i;
while(vis[v] != i && id[v] == -1 && v != root) {
vis[v] = i;
v = pre[v];
}
if(v != root && id[v] == -1) {
for(int u = pre[v]; u != v; u = pre[u])
id[u] = cnt;//标记节点u为第几个环
id[v] = cnt++;
}
}
if(cnt == 0)
break; //无环 则break
for( i = 0; i < V; i++)
if(id[i] == -1)
id[i] = cnt++;
//3.建立新图 缩点,重新标记
for( i = 0; i < E; i++) {
int u = edge[i].u;
int v = edge[i].v;
edge[i].u = id[u];
edge[i].v = id[v];
if(id[u] != id[v])
edge[i].w -= in[v];
}
V = cnt;
root = id[root];
}
return ret;
}
复制代码例题
【题解】Command Network POJ – 3164 ⭐⭐⭐ 【最小树形图】
After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.
With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node A to another node B, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.
Input
The input contains several test cases. Each test case starts with a line containing two integer N (N ≤ 100), the number of nodes in the destroyed network, and M (M ≤ 104), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair xi and yi, giving the Cartesian coordinates of the nodes. Then follow M lines each containing two integers i and j between 1 and N (inclusive) meaning a wire can be built between node i and node j for unidirectional command delivery from the former to the latter. littleken’s headquarter is always located at node 1. Process to end of file.
Output
For each test case, output exactly one line containing the shortest total length of wires to two digits past the decimal point. In the cases that such a network does not exist, just output ‘poor snoopy’.
Examples
Sample Input
4 6
0 6
4 6
0 0
7 20
1 2
1 3
2 3
3 4
3 1
3 2
4 3
0 0
1 0
0 1
1 2
1 3
4 1
2 3
Sample Output
31.19
poor snoopy
题意:
给出有向图的N个点和M条边, 求最小树形图, 无法求出输出poor snoopy
题解:
这道题时间卡的不严, 前面的两个模板都可以用
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef long long LL;
const int inf = 1<<30;
const LL maxn = 110;
int N, M;
double w[maxn][maxn];
struct node{
double x, y;
}vs[maxn];
double getDis(int x1, int y1, int x2, int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
bool vis[maxn], flag[maxn];
int pre[maxn];
double zhuliu(int u){
ms(vis, 0);
double ans = 0;
while(true){
for(int i = 1; i <= N; ++i)
if(i!=u && !flag[i]){
w[i][i] = inf, pre[i] = i;
for(int j = 1; j <= N; ++j)
if(!flag[j] && w[j][i] < w[pre[i]][i])
pre[i] = j;
if(pre[i] == i) return -1;
}
int i;
for(i = 1; i <= N; ++i){
if(i!=u && !flag[i]){
int j = i, cnt = 0;
while(j!=u && pre[j]!=i && cnt<=N)
j = pre[j], ++cnt;
if(j==u || cnt>N) continue;
break;
}
}
if(i > N){
for(int i = 1; i <= N; ++i)
if(i!=u && !flag[i])
ans += w[pre[i]][i];
return ans;
}
int j = i;
ms(vis, 0);
do{
ans += w[pre[j]][j], j = pre[j], vis[j] = flag[j] = true;
}while(j != i);
flag[i] = false;
for(int k = 1; k <= N; ++k)
if(vis[k]){
for(int j = 1; j <= N; ++j)
if(!vis[j]){
if(w[i][j] > w[k][j])
w[i][j] = w[k][j];
if(w[j][k] < inf && w[j][k]-w[pre[k]][k] < w[j][i])
w[j][i] = w[j][k] - w[pre[k]][k];
}
}
}
return ans;
}
int main()
{
int a, b;
while(scanf("%d%d",&N,&M)!=EOF){
ms(vis, 0); ms(flag, 0);
fill(w[0], w[0]+maxn*maxn, inf);
for(int i = 1; i <= N; ++i)
scanf("%lf%lf",&vs[i].x,&vs[i].y);
for(int i = 1; i <= M; ++i){
scanf("%d%d",&a,&b);
w[a][b] = getDis(vs[a].x, vs[a].y, vs[b].x, vs[b].y);
}
double ans = zhuliu(1);
if(ans==-1) printf("poor snoopy\n");
else printf("%.2f\n",ans);
}
return 0;
}
复制代码
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
