คัดลอกรหัสรหัสดังต่อไปนี้:
-
เทมเพลตแผนผังต้นไม้ขั้นต่ำ - อัลกอริธึม Zhu Liu
คำอธิบายเทมเพลต: ป้ายกำกับจุดต้องเป็น 0-(N-1)
ต้องลบจุดไปที่ตัวมันเอง (น้ำหนักขอบของขอบถึงตัวมันเองนั้นไม่มีที่สิ้นสุด)
-
#กำหนดเอ็ม109
#กำหนดประเภทint
ประเภท const inf=(1)<<30;
โหนดโครงสร้าง {
int คุณ v;
ต้นทุนประเภท;
}อี[ม*ม+5];
int ก่อน[M],ID[M],vis[M];
พิมพ์ใน[M];
int n,m;
พิมพ์ Directed_MST (int root, int NV, int NE) {
พิมพ์ ret = 0;
ในขณะที่ (จริง) {
//1. ค้นหาขอบทางเข้าที่เล็กที่สุด
สำหรับ (int i = 0; i <NV; i ++) ใน [i] = inf;
สำหรับ(int i=0;i<NE;i++){
int คุณ = E[i].u;
int v = E[i].v;
ถ้า (E [i] .cost < ใน [v] && u != v) {
ก่อน[v] = คุณ;
ใน[v] = E[i].ต้นทุน;
-
-
สำหรับ(int i=0;i<NV;i++) {
ถ้า (i == root) ดำเนินการต่อ;
if(In[i] == inf)return -1;//ไม่มีขอบขาเข้ายกเว้นจุดต่อไปนี้ ดังนั้นรูทไม่สามารถเข้าถึงได้
-
//2. ค้นหาแหวน
int cntnode = 0;
memset(ID,-1,ขนาดของ(ID));
memset(vis,-1,ขนาดของ(vis));
ใน [รูท] = 0;
for(int i=0;i<NV;i++) {//ทำเครื่องหมายแต่ละวง
ret += ใน [i];
int วี = ฉัน;
ในขณะที่ (vis [v] ! = i && ID [v] == -1 && v != root) {
วิส[วี] = ฉัน;
โวลต์ = ก่อน[วี];
-
ถ้า (v != รูท && ID [v] == -1) {
สำหรับ(int u = pre[v] ; u != v ; u = pre[u]) {
ID[u] = cntnode;
-
ID[v] = cntnode++;
-
-
if(cntnode == 0)break;//ไม่มีการวนซ้ำ
สำหรับ(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 = ไอดี[E[i].u];
E[i].v = ไอดี[E[i].v];
ถ้า(E[i].u != E[i].v) {
E[i].ต้นทุน -= ใน[v];
-
-
NV = cntnode;
รูท = ID [รูท];
-
กลับมาอีกครั้ง;
-