最小樹形圖模板朱劉算法分享

最小樹形圖模板朱劉算法分享。本站提示廣大學習愛好者：（最小樹形圖模板朱劉算法分享）文章只能為提供參考，不一定能成為您想要的結果。以下是最小樹形圖模板朱劉算法分享正文

/*
最小樹形圖圖模版-朱劉算法
模版解釋：點標號必需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;
}