最小树形图模板朱刘算法分享

/*
最小树形图图模版-朱刘算法
模版说明：点标号必须0-(n-1)
   必须去除到自身的点（到自身的边的边权赋无限大）
*/
#define m 109
#define type int
const type inf=(1)<<30;
struct node{
 int u , v;
 type cost;
}e[m*m+5];
int pre[m],id[m],vis[m];
type in[m];
int n,m;
type directed_mst(int root,int nv,int ne) {
 type ret = 0;
 while(true) {
  //1.找最小入边
  for(int i=0;i<nv;i++) in[i] = inf;
  for(int i=0;i<ne;i++){
   int u = e[i].u;
   int v = e[i].v;
   if(e[i].cost < in[v] && u != v) {
    pre[v] = u;
    in[v] = e[i].cost;
   }
  }
  for(int i=0;i<nv;i++) {
   if(i == root) continue;
   if(in[i] == inf) return -1;//除了跟以外有点没有入边,则根无法到达它
  }
  //2.找环
  int cntnode = 0;
 memset(id,-1,sizeof(id));
 memset(vis,-1,sizeof(vis));
  in[root] = 0;
  for(int i=0;i<nv;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] = cntnode;
    }
    id[v] = cntnode ++;
   }
  }
  if(cntnode == 0) break;//无环
  for(int i=0;i<nv;i++) if(id[i] == -1) {
   id[i] = cntnode ++;
  }
  //3.缩点,重新标记
  for(int i=0;i<ne;i++) {
   int v = e[i].v;
   e[i].u = id[e[i].u];
   e[i].v = id[e[i].v];
   if(e[i].u != e[i].v) {
    e[i].cost -= in[v];
   }
  }
  nv = cntnode;
  root = id[root];
 }
 return ret;
}