次のようにコードをコピーします。
/*
最小樹形図テンプレート - Zhu Liu アルゴリズム
テンプレートの説明: ポイント ラベルは 0-(N-1) である必要があります
それ自体へのポイントは削除する必要があります (それ自体へのエッジのエッジの重みは無限大です)
*/
#定義M109
#int 型を定義します
const type inf=(1)<<30;
構造体ノード{
int u 、 v;
タイプのコスト。
}E[M*M+5];
int pre[M],ID[M],vis[M];
「In[M]」と入力します。
int n,m;
type Directed_MST(int root,int NV,int NE) {
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].コスト;
}
}
for(int i=0;i<NV;i++) {
if(i == root) 続行;
if(In[i] == inf)return -1;//次の点以外に入力エッジがないため、ルートはそれに到達できません
}
//2. 指輪を見つける
int cntnode = 0;
memset(ID,-1,sizeof(ID));
memset(vis,-1,sizeof(vis));
[ルート] = 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 = 前[v];
}
if(v != ルート && 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;
ルート = ID[ルート];
}
retを返します。
}