朱刘算法---有向图的最小生成树

出处 http://blog.csdn.net/wsniyufang/article/details/6747406

 1 /*
 2 最小树形图图模版-朱刘算法
 3 模版说明：点标号必须0-(N-1)
 4          必须去除到自身的点（到自身的边的边权赋无限大）
 5 */
 6 #define M 109
 7 #define type int
 8 const type inf=(1)<<30;
 9 struct Node{
10     int u , v;
11     type cost;
12 }E[M*M+5];
13 int pre[M],ID[M],vis[M];
14 type In[M];
15 int n,m; 
16 type Directed_MST(int root,int NV,int NE) {
17     type ret = 0;
18     while(true) {
19         //1.找最小入边
20         for(int i=0;i<NV;i++) In[i] = inf;
21         for(int i=0;i<NE;i++){
22             int u = E[i].u;
23             int v = E[i].v;
24             if(E[i].cost < In[v] && u != v) {
25                 pre[v] = u;
26                 In[v] = E[i].cost;
27             }
28         }
29         for(int i=0;i<NV;i++) {
30             if(i == root) continue;
31             if(In[i] == inf)    return -1;//除了跟以外有点没有入边,则根无法到达它
32         }
33         //2.找环
34         int cntnode = 0;
35     memset(ID,-1,sizeof(ID));
36     memset(vis,-1,sizeof(vis));
37         In[root] = 0;
38         for(int i=0;i<NV;i++) {//标记每个环
39             ret += In[i];
40             int v = i;
41             while(vis[v] != i && ID[v] == -1 && v != root) {
42                 vis[v] = i;
43                 v = pre[v];
44             }
45             if(v != root && ID[v] == -1) {
46                 for(int u = pre[v] ; u != v ; u = pre[u]) {
47                     ID[u] = cntnode;
48                 }
49                 ID[v] = cntnode ++;
50             }
51         }
52         if(cntnode == 0)    break;//无环
53         for(int i=0;i<NV;i++) if(ID[i] == -1) {
54             ID[i] = cntnode ++;
55         }
56         //3.缩点,重新标记
57         for(int i=0;i<NE;i++) {
58             int v = E[i].v;
59             E[i].u = ID[E[i].u];
60             E[i].v = ID[E[i].v];
61             if(E[i].u != E[i].v) {
62                 E[i].cost -= In[v];
63             }
64         }
65         NV = cntnode;
66         root = ID[root];
67     }
68     return ret;
69 }