انسخ رمز الكود كما يلي:
/*
الحد الأدنى لقالب مخطط الشجرة - خوارزمية Zhu Liu
وصف القالب: يجب أن تكون تسمية النقطة 0-(N-1)
يجب إزالة النقاط لنفسها (وزن الحافة لنفسها لا نهائي)
*/
#تعريف م109
# تحديد النوع int
نوع ثابت inf=(1)<<30;
عقدة الهيكل {
إنت ش، الخامس؛
تكلفة النوع؛
}ه[م*م+5];
int pre[M],ID[M],vis[M];
اكتب في [م]؛
كثافة العمليات ن، م؛
اكتب Directed_MST(int root,int NV,int NE) {
اكتب ريت = 0؛
بينما (صحيح) {
//1. ابحث عن أصغر حافة دخول
for(int i=0;i<NV;i++) In[i] = inf;
ل(int i=0;i<NE;i++){
int u = E[i].u;
int v = E[i].v;
إذا (E[i].cost < In[v] && u != v) {
قبل[v] = u;
In[v] = E[i].cost;
}
}
ل(int i=0;i<NV;i++) {
إذا استمر (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) {
فيس[v] = i;
v = قبل[v];
}
إذا (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. تقليص النقاط وإعادة وضع علامة
ل(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];
إذا (E[i].u != E[i].v) {
E[i].cost -= In[v];
}
}
NV = cntnode;
الجذر = معرف[الجذر]؛
}
عودة متقاعد؛
}