Copiez le code comme suit :
/*
Modèle d'arborescence minimale - Algorithme Zhu Liu
Description du modèle : l'étiquette du point doit être 0-(N-1)
Les points vers lui-même doivent être supprimés (le poids du bord sur lui-même est infini)
*/
#définir M 109
#définir le type int
type const inf=(1)<<30;
Nœud de structure{
int tu , v;
tapez le coût ;
}E[M*M+5];
int pré[M],ID[M],vis[M];
tapez In[M] ;
int n,m;
tapez Directed_MST (racine int, int NV, int NE) {
tapez ret = 0 ;
tandis que (vrai) {
//1. Trouver le plus petit bord d'entrée
pour(int i=0;i<NV;i++) In[i] = inf;
pour(int i=0;i<NE;i++){
int u = E[i].u;
int v = E[i].v;
si(E[i].cost < In[v] && u != v) {
pré[v] = vous;
In[v] = E[i].coût ;
}
}
pour(int i=0;i<NV;i++) {
if(i == racine) continue ;
if(In[i] == inf)return -1;//Il n'y a pas d'arête entrante sauf le point suivant, alors la racine ne peut pas l'atteindre
}
//2. Trouvez la bague
int cntnode = 0;
memset(ID,-1,sizeof(ID));
memset(vis,-1,sizeof(vis));
Dans[racine] = 0 ;
for(int i=0;i<NV;i++) {//Marque chaque anneau
ret += Dans[i];
int v = je;
while(vis[v] != i && ID[v] == -1 && v != racine) {
vis[v] = je;
v = pré[v];
}
si(v != racine && ID[v] == -1) {
pour(int u = pré[v] ; u != v ; u = pré[u]) {
ID[u] = cntnode ;
}
ID[v] = cntnode++;
}
}
if(cntnode == 0)break;//Pas de boucle
pour(int i=0;i<NV;i++) if(ID[i] == -1) {
ID[i] = cntnode++;
}
//3. Réduire les points et re-marquer
pour(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];
si(E[i].u != E[i].v) {
E[i].coût -= Dans[v];
}
}
NV = nœud cnt;
racine = ID[racine];
}
retour à la retraite;
}