朱

· 定义

　　对于有向无环图$G (V, E)$，类似最小生成树的定义，有向图最小树形图即在有向图上查找总权值和最小的树形图（即有向边的树）。

· 朱 - 刘算法

　　对于每个点先选取到达它的最小的边，这样可组成一个边集E₁，显然，该边集权值和最小，但不一定是树。

　　在该边集上进行缩点，并判断是否有解（是否有点无入度，或若有根无出度），在融会$G$中，记为G₁。

　　当然，若此时没有找到有向环且有解，说明在当前图上已找到最小树形图，那么将原来的缩点解开，即除了当前树形图上的弧之外，将缩点内没有与已知弧有相同终点的边选出，如此构成了G的最小树形图。

　　反之，则进行改边：先省去缩点内边；对于由缩点内出去的边，保持原权值即可；对于进入缩点的边，令V_s表示缩点点集，对于∀v ∈ V_s，∀u ∉ V_s，有<u, V> = <u, v> - v的最小入权边，是因为这样将权值相加的话，就相当于删去了缩点中拥有相同终点的边。

　　这样更改完点集与边集，进行重复运算即可。

　　对于无根树，建立超级根节点即可。

　　其中，复杂度$O (nm)$。

· 代码

　　（该代码仅求最小权值总和，这样是不需解开缩点的）

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 
  7 typedef long long LL;
  8 
  9 const int MAXN = 100 + 10;
 10 const int MAXM = 1e04 + 10;
 11 
 12 const int INF = 0x7fffffff;
 13 
 14 struct Edge {
 15     int u, v;
 16     int w;
 17     
 18     Edge () {}
 19     
 20     Edge (int fu, int fv, int fw) :
 21         u (fu), v (fv), w (fw) {}
 22 } ;
 23 
 24 Edge Edges[MAXM];
 25 
 26 LL ans = 0;
 27 
 28 int Inw[MAXN];
 29 int pre[MAXN];
 30 
 31 int Belong[MAXN];
 32 int Vis[MAXN];
 33 
 34 void Zhu_Liu (int root, int V, int E) {
 35     while (true) {
 36         for (int i = 1; i <= V; i ++)
 37             Inw[i] = INF;
 38         
 39         for (int i = 1; i <= E; i ++) {
 40             int u = Edges[i].u;
 41             int v = Edges[i].v;
 42             int w = Edges[i].w;
 43             
 44             if (u == v)
 45                 continue;
 46             
 47             if (w < Inw[v]) {
 48                 Inw[v] = w;
 49                 pre[v] = u;
 50             }
 51         }
 52         
 53         for (int i = 1; i <= V; i ++)
 54             if (Inw[i] == INF && i != root) {
 55                 ans = - 1;
 56                 
 57                 return ;
 58             }
 59         
 60         memset (Belong, - 1, sizeof (Belong));
 61         memset (Vis, - 1, sizeof (Vis));
 62         Inw[root] = 0;
 63         
 64         int cnt = 0;
 65         for (int i = 1; i <= V; i ++) {
 66             ans += Inw[i];
 67             
 68             int pres = i;
 69             while (Vis[pres] != i && Belong[pres] == - 1 && pres != root) {
 70                 Vis[pres] = i;
 71                 pres = pre[pres];
 72             }
 73             
 74             if (Belong[pres] == - 1 && pres != root) {
 75                 cnt ++;
 76                 for (int p = pre[pres]; p != pres; p = pre[p])
 77                     Belong[p] = cnt;
 78                 Belong[pres] = cnt;
 79             }
 80         }
 81         
 82         if (! cnt)
 83             break;
 84         
 85         for (int i = 1; i <= V; i ++)
 86             if (Belong[i] == - 1)
 87                 Belong[i] = ++ cnt;
 88         
 89         for (int i = 1; i <= E; i ++) {
 90             int u = Edges[i].u;
 91             int v = Edges[i].v;
 92             
 93             Edges[i].u = Belong[u];
 94             Edges[i].v = Belong[v];
 95             
 96             if (Belong[u] != Belong[v])
 97                 Edges[i].w -= Inw[v];
 98         }
 99         
100         V = cnt;
101         root = Belong[root];
102     }
103 }
104 
105 int N, M, Root;
106 
107 int Outdeg[MAXN]= {0};
108 
109 int main () {
110     scanf ("%d%d%d", & N, & M, & Root);
111     
112     for (int i = 1; i <= M; i ++) {
113         int u, v, w;
114         scanf ("%d%d%d", & u, & v, & w);
115         
116         Edges[i] = Edge (u, v, w);
117         Outdeg[u] ++;
118     }
119     
120     if (! Outdeg[Root])
121         ans = - 1;
122     else
123         Zhu_Liu (Root, N, M);
124     
125     printf ("%lld
", ans);
126     
127     return 0;
128 }
129 
130 /*
131 4 6 1
132 1 2 3
133 1 3 1
134 4 1 2
135 4 2 2
136 3 2 1
137 3 4 1
138 */
139 
140 /*
141 4 6 3
142 1 2 3
143 1 3 1
144 4 1 2
145 4 2 2
146 3 2 1
147 3 4 1
148 */
149 
150 /*
151 4 6 2
152 1 2 3
153 1 3 1
154 4 1 2
155 4 2 2
156 3 2 1
157 3 4 1
158 */

View Code