# one

### An overview of the

`Minimum tree graph, in short, is to find the minimum spanning tree of directed weighted graph. The official definition is as follows: The minimum tree graph is to specify a special point root in the weighted directed graph, and find a directed spanning tree T with root as the root, and the total weight of all edges in T is the minimum.Copy the code`

A general solution of the minimum tree graph algorithm is in 1965 Zhu Yongjin and Liu Zhenhong proposed the complexity of O(VE) algorithm: Zhu, Liu algorithm. Today we’re going to talk about the smallest tree.

Minimum tree graph, in short, is to find the minimum spanning tree of directed weighted graph. The official definition is as follows: The minimum tree graph is to specify a special point root in the weighted directed graph, and find a directed spanning tree T with root as the root, and the total weight of all edges in T is the minimum.

### Giulio givanni carlo taccon algorithm

Big problem on the complete zhu, liu algorithm is composed of four major steps: 1, the shortest arc set E 2, judge set E there have to ring, if you have to step 3, otherwise turn 4 points 3, contraction, to have to ring shrinkage as a point, and to rebuild, including edge weights change and some processing, and then turn to step 1. 4. Expand the shrinkage point to obtain the minimum tree diagram. Tips: The algorithm is described in detail

In general, ACM is concerned with the weight problem of the minimum tree graph of the expedition team, so step 4 is generally omitted, and the weight sum of its ring can be processed in the intermediate process. So we won’t talk much about step 4 here.

### Algorithm,

1, first of all, we first set the shortest arc E, for the current figure if there are n points (a directed ring contraction point count as one point), we will choose the n – 1 point, determine its into the edge of the shortest edge, composed of its a set we are called the shortest arc set E, if we are enumerated to a certain point of time, it has no into the edge, it means that there is no minimum tree, So this is the end of the algorithm, and we go back to the main function.

```
for(int i = 1; i <= n; i++)
if(i ! = u && ! flag[i]) {//u is the root node, flag[I] is 1, indicating that the point is in a directed loop and is not a representative point of the directed loop.
w[i][i] = INF, pre[i] = i; // Initialize the precursors of the current point to itself
for(int j = 1; j <= n; j++)// Enumerate the precursors of I (the points from j to I) and add them to the set E
if(! flag[j] && w[j][i] < w[pre[i]][i]) { pre[i] = j;// Update the precursors of the current point to j
}
// If the current point I has no edge, then there is no minimum tree graph.
if(pre[i] == i)
return - 1;
Copy the code
```

2. Then we judge the edges in set E to determine whether there are directed loops. There is a store of precursors in the code implementation, so in this part, we can enumerate the precursors directly forward. If the precursors of the enumeration can finally enumerate to the root node, then there is no directed loop in this part. Otherwise, we can enumerate each point forward.

```
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;// For each node, look for the precursor node and see if it can form a loop
if(j == u || cnt > n)
continue; // If you can return to the root or pass through more than n points, there is no directed loop
break; // Otherwise, there is a directed loop}}Copy the code
```

3. If there is a directed ring, we need to shrink the points of the directed ring. Since we found that there is a directed ring when we enumerate to node I, we might as well shrink the points inside the directed ring to point I. A new graph will be formed after the contraction, and the change pattern of the graph is as follows:

Map [k][u]=w; map[k][I]=w-w2; map[k][I]=w-w2;

If map[k][j] <map[I][j], map[I][j]=map[k][j], then map[I][j]=map[k][j]. If map[k][j] =map[k][j] For the just three steps: shrinkage point, the edge weight of the new graph processed by the shrinkage point, and the edge weight of the final processing point I based on greedy thought, we can combine the last two into one operation, and their respective code implementation:

```
int j = i;
memset(vis, 0.sizeof(vis));
do {
// Mark the points inside the ring, and add the weights of the ring directly. When the smallest tree is found at the end, there is no need to expand the shrink point
ans += w[pre[j]][j], j = pre[j], vis[j] = flag[j] = true;
} while(j ! = i); flag[i] =false; // The ring shrinks to point I, but point I still exists
Copy the code
```

Tips: Shrink solutions are not unique

4. The graph formed after processing the shrinkage point:

```
for(int k = 1; k <= n; ++k)
if(vis[k]) { // The point in the ring is already marked when the point in the ring is contracted.
for(int j = 1; j <= n; j++)
if(! vis[j]) {// Points not in the ring
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]; }}Copy the code
```

After processing 4, we go back to step 1 and continue to search for the minimum arc set E. Finally, after finding a minimum arc set E without a ring, all edges in the set E without arc (including the edges that can expand the shrinkage point) are the edge set of the minimum tree we want. Because our ACM general o is the value of minimum tree diagram, so we usually don’t need a contraction in the treatment of the ring, it is good to record the edge weights directly, when it finds a set without ring E, to add the last edge weights and can, for the last part of the weighted, code:

```
if(i > n) {
// This piece of code follows code 2. If all points are enumerated and no directed loop is found, then the final set is found.
for(int i = 1; i <= n; i++)
if(i ! = u && ! flag[i]) ans += w[pre[i]][i];// Add up all the edges in the final set E.
return ans;
}
Copy the code
```

The complete code implementation of Zhu and Liu’s algorithm (the adjacencies matrix version without expansion shrinkage points) :

```
bool vis[maxn], flag[maxn];
int pre[maxn];
void init(a) { / / initialization
memset(vis, 0.sizeof(vis));
memset(flag, 0.sizeof(flag));
fill(w[0], w[0] + maxn * maxn, inf);
}
double directed_mst(int u) { // U is the root node
double ans = 0;
memset(vis, 0.sizeof(vis));
while(true) {
// Find the shortest arc set 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;// We can also use DFS preprocessing to determine convex connectivity
}
// Check whether E has a ring
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; // If you can return to the root or pass through more than n points, there is no directed loop
break; }}if(i > n) {
for(int i = 1; i <= n; i++)
if(i ! = u && ! flag[i]) ans += w[pre[i]][i];return ans;
}
// You have a ring, you shrink it, you shrink the whole ring to a point I.
int j = i;
memset(vis, 0.sizeof(vis));
do {
// Mark the points inside the ring, and add the weights of the ring directly. When the smallest tree is found at the end, there is no need to expand the shrink point
ans += w[pre[j]][j], j = pre[j], vis[j] = flag[j] = true;
} while(j ! = i); flag[i] =false; // The ring shrinks to point I, but point I still exists
// At the same time, the edge weights are changed
for(int k = 1; k <= n; ++k)
if(vis[k]) { // Points in the ring
for(int j = 1; j <= n; j++)
if(! vis[j]) {// Points not in the ring
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;
}
Copy the code
```

`< span style = "margin-bottom: 0pt; margin-bottom: 0pt; margin-bottom: 0pt;Copy the code`

Reference: www.cnblogs.com/xzxl/p/7243…

# The second

### 1. Relevant definitions

Definition: let G = (V,E) be a directed graph with the following properties: 1. 2. If there is a vertex vi, which is not the end of any arc, and the other vertices in V happen to be the end of a unique arc, then G is said to be a tree rooted in vi. The minimum tree graph is the one with the smallest sum of weights in the tree graph with roots vi in the directed graph G = (V, E).

Another way of saying it: the minimum tree graph is to give a weighted directed graph a special point root, find a tree root node such that the total weight of the tree is the smallest. Properties: The minimum tree graph is based on the idea of greed and shrinking points. Shrink point: Consider several points as one point. All edges connected to these points are considered to be connected to the shrink point. All edges connected from these points are considered to be connected to the shrink point

### 2. Algorithm description

【 Overview 】 In order to find the minimum tree graph of a graph, ① First find the shortest arc set E0; (2) If E0 does not exist, then the minimum tree of the graph does not exist; (3) If E0 exists and does not have a ring, then E0 is the smallest tree graph; (4) if the E0 exists but have to ring, then the ring u shrink into a point, to form a new figure G1, then the G1 to continue its minimum tree, until to figure Gi, if Gi do not have minimum tree, so the figure there is no minimum tree diagram, if Gi is minimum tree, then the drill-down, had the smallest tree diagram of the original image.

Let the root node be v0, ○ (1) find the shortest arc set E0 from all the arc ending with vi(I ≠ 0), if for point I, there is no edge, then there is no minimum tree graph, the algorithm ends; If you can, you get a subgraph G’ of a graph G with n points and n minus 1 edges, which must have the smallest weight, but not necessarily a tree.

○ (2) Check E0. If E0 has no directed ring and does not contain shrinkage points, then the calculation is finished. E0 is the minimum tree of graph G with v0 as the root; If E0 contains a directed loop, go to step (3); If E0 does not have a directional ring, but there is a shrinkage point, go to step (4).

○ (3) Contracting the directed ring in G by contracting the ring C in G to point U, the edges in G with both ends belonging to C will be contracted, and the other arc will remain, resulting in a new graph G1, in which the length of the arc terminating at the contracting point will change. The rule is as follows: if point v is in ring C, and the weight of the edge pointing to v is w, and point V ‘is not in ring C, then for every edge <v’, v> in G, there is edge <v’, u> corresponding to it in G1, and the weight WG1(<v’, u>) = WG(<v’, v>) -w; For a graph G with a starting point of the edge of ring in C, v >, < v ‘in figure G1 has’ >, < u, v, WG1 (‘ > < u, v) = WG (< v’, v >). It is important to note that the generated graph G1 may have multiple edges. For graphs G and G1: (1) If there is no minimum tree graph with root v0 in graph G1, then there is no smallest tree graph in graph G; (2) If there is a minimum tree graph in G1 with v0 as the root, the minimum tree graph of graph G can be obtained according to the expansion method in Step (4). Therefore, the minimum tree graph of graph G1 should be substituted into (1) repeatedly until the minimum tree graph u of G1 is solved.

○ (4) Expand shrinkage point Assume that the minimum tree of graph G1 is T1, then all arcs in T1 belong to the minimum tree T of graph G. A contraction point u of G1 is expanded into a ring C, and the arc with the same end point as T1 is removed from C. All other arcs belong to T.

[Summary] Make a small summary of the minimum tree graph: 1: clear the self-loop, self-loop is impossible to exist in any minimum tree graph; 2: find the minimum edge of each vertex; 3: Judge whether there is a minimum tree graph in the graph, which can be determined by 1, or the graph can be determined whether there is a minimum tree graph by taking the vertex V in the graph as the root node to traverse the graph; 4: find the ring, and then create a new picture, after the indentation re-mark.

```
struct node { // Edge weights and vertices
int u, v;
type w;
} edge[MAXN * MAXN];
int pre[MAXN], id[MAXN], vis[MAXN], n, m;
type in[MAXN];// Save the minimum edge weight,pre[v] is the starting point of the edge
type Directed_MST(int root, int V, int E) {
type ret = 0;// Save the total weight of the minimum tree
while(true) {
int i;
//1. Find the minimum entry edge of each node
for( i = 0; i < V; i++)
in[i] = INF;// Initialize to infinity
for( i = 0; i < E; i++) { // Iterate over each edge
int u = edge[i].u;
int v = edge[i].v;
if(edge[i].w < in[v] && u ! = v) {// Note that vertex v has an incoming edge with a small weight
pre[v] = u;// Node u points to v
in[v] = edge[i].w;// Minimum edge entry}}for( i = 0; i < V; i++) { // Determine whether the minimum tree graph exists
if(i == root)
continue;
if(in[i] == INF)
return - 1;// If there is no edge except for the root, then the root cannot reach it. This means that it is an independent point and must not form the tree
}
/ / 2. Looking for a ring
int cnt = 0;// Record the ring number
memset(id, - 1.sizeof(id));
memset(vis, - 1.sizeof(vis));
in[root] = 0;
for( i = 0; i < V; i++) { // Mark each ring
ret += in[i];// Record the weight
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(intu = pre[v]; u ! = v; u = pre[u]) id[u] = cnt;// Mark the ring of the node uid[v] = cnt++; }}if(cnt == 0)
break; // if there is no ring, break
for( i = 0; i < V; i++)
if(id[i] == - 1)
id[i] = cnt++;
//3. Create a new indent and re-label it
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;
}
Copy the code
```

## sample

## 【 解 析 】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 KnuthOcean’s force has 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 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 Output 4 6 0 6 4 6 0 0 7 20 1 2 1 3 3 3 3 3 3 3 3 3 4 3 0 0 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 Sample Output 31.19 poor snoopy

#### The question:

Given N points and M edges of a directed graph, find the smallest tree graph, unable to find the output of Poor snoopy

#### Answer key:

The time card of this problem is not strict, the two templates in front can be used

```
#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(a)
{
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;
}
Copy the code
```