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

/*
最小树形图图模版-朱刘算法
模版说明：点标号必须0-(N-1)
  必须去除到自身的点（到自身的边的边权赋无限大）
*/
#defineM109
#definetypeint
consttypeinf=(1)<<30;
structNode{
 intu,v;
 typecost;
}E[M*M+5];
intpre[M],ID[M],vis[M];
typeIn[M];
intn,m;
typeDirected_MST(introot,intNV,intNE){
 typeret=0;
 while(true){
  //1.找最小入边
  for(inti=0;i<NV;i++)In[i]=inf;
  for(inti=0;i<NE;i++){
   intu=E[i].u;
   intv=E[i].v;
   if(E[i].cost<In[v]&&u!=v){
    pre[v]=u;
    In[v]=E[i].cost;
   }
  }
  for(inti=0;i<NV;i++){
   if(i==root)continue;
   if(In[i]==inf) return-1;//除了跟以外有点没有入边,则根无法到达它
  }
  //2.找环
  intcntnode=0;
 memset(ID,-1,sizeof(ID));
 memset(vis,-1,sizeof(vis));
  In[root]=0;
  for(inti=0;i<NV;i++){//标记每个环
   ret+=In[i];
   intv=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]=cntnode;
    }
    ID[v]=cntnode++;
   }
  }
  if(cntnode==0) break;//无环
  for(inti=0;i<NV;i++)if(ID[i]==-1){
   ID[i]=cntnode++;
  }
  //3.缩点,重新标记
  for(inti=0;i<NE;i++){
   intv=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];
 }
 returnret;
}