다음과 같이 코드 코드를 복사합니다.
/*
최소 트리 다이어그램 템플릿 - Zhu Liu 알고리즘
템플릿 설명: 포인트 라벨은 0-(N-1)이어야 합니다.
자신에 대한 점은 제거되어야 합니다(자체에 대한 간선의 간선 가중치는 무한합니다).
*/
#M 109 정의
#정의 유형 int
const 유형 inf=(1)<<30;
구조체 노드{
int 당신, v;
유형 비용;
}E[M*M+5];
int pre[M],ID[M],vis[M];
입력[M];
int n,m;
유형 Directed_MST(int 루트,int NV,int NE) {
ret = 0을 입력하세요.
동안(참) {
//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) {
사전[v] = u;
In[v] = E[i].cost;
}
}
for(int i=0;i<NV;i++) {
if(i == 루트) 계속;
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 != 루트) {
비스[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 = cnt노드;
루트 = 아이디[루트];
}
반환 ret;
}