最小樹(shù)形圖模板朱劉算法分享
更新時(shí)間：2014年01月22日 15:21:11 作者：
這篇文章主要介紹了最小樹(shù)形圖模板朱劉算法，有需要的朋友可以參考一下
復(fù)制代碼 代碼如下:
/*
最小樹(shù)形圖圖模版-朱劉算法
模版說(shuō)明：點(diǎn)標(biāo)號(hào)必須0-(N-1)
必須去除到自身的點(diǎn)（到自身的邊的邊權(quán)賦無(wú)限大）
*/
#define M 109
#define type int
const type inf=(1)<<30;
struct Node{
int u , v;
type cost;
}E[M*M+5];
int pre[M],ID[M],vis[M];
type In[M];
int n,m;
type Directed_MST(int root,int NV,int NE) {
type 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].cost;
}
}
for(int i=0;i<NV;i++) {
if(i == root) continue;
if(In[i] == inf) return -1;//除了跟以外有點(diǎn)沒(méi)有入邊,則根無(wú)法到達(dá)它
}
//2.找環(huán)
int cntnode = 0;
memset(ID,-1,sizeof(ID));
memset(vis,-1,sizeof(vis));
In[root] = 0;
for(int i=0;i<NV;i++) {//標(biāo)記每個(gè)環(huán)
ret += In[i];
int v = i;
while(vis[v] != i && ID[v] == -1 && v != root) {
vis[v] = i;
v = pre[v];
}
if(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;//無(wú)環(huán)
for(int i=0;i<NV;i++) if(ID[i] == -1) {
ID[i] = cntnode ++;
}
//3.縮點(diǎn),重新標(biāo)記
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;
root = ID[root];
}
return ret;
}
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了java客戶端登陸服務(wù)器用戶名驗(yàn)證的相關(guān)資料,需要的朋友可以參考下2016-05-05
IntelliJ IDEA創(chuàng)建普通的Java 項(xiàng)目及創(chuàng)建 Java 文件并運(yùn)行的教程
這篇文章主要介紹了IntelliJ IDEA創(chuàng)建普通的Java 項(xiàng)目及創(chuàng)建 Java 文件并運(yùn)行的教程,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-02-02
Java實(shí)現(xiàn)線程的暫停和恢復(fù)的示例詳解
這幾天的項(xiàng)目中,客戶給了個(gè)需求,希望我可以開(kāi)啟一個(gè)任務(wù),想什么時(shí)候暫停就什么時(shí)候暫停,想什么時(shí)候開(kāi)始就什么時(shí)候開(kāi)始,所以本文小編給大家介紹了Java實(shí)現(xiàn)線程的暫停和恢復(fù)的示例,需要的朋友可以參考下2023-11-11
Spring DATA JPA 中findAll 進(jìn)行OrderBy方式
這篇文章主要介紹了Spring DATA JPA 中findAll 進(jìn)行OrderBy方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-11-11
Java調(diào)用shell腳本解決傳參和權(quán)限問(wèn)題的方法
今天小編就為大家分享一篇關(guān)于Java調(diào)用shell腳本解決傳參和權(quán)限問(wèn)題的方法，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-03-03
Eclipse 2020-06 漢化包安裝步驟詳解（附漢化包+安裝教程）
這篇文章主要介紹了Eclipse 2020-06 漢化包安裝步驟（附漢化包+安裝教程）,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-08-08
這篇文章主要介紹了Java反射機(jī)制的簡(jiǎn)單講解,本文講解了Java的高級(jí)概念反射機(jī)制,通過(guò)文字介紹案例該項(xiàng)概念和代碼的詳細(xì)展示,需要的朋友可以參考下2021-07-07
java過(guò)濾html標(biāo)簽獲取純文本信息的實(shí)例
今天小編就為大家分享一篇java過(guò)濾html標(biāo)簽獲取純文本信息的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-05-05
Spring Cloud中使用Feign,@RequestBody無(wú)法繼承的解決方案
這篇文章主要介紹了Spring Cloud中使用Feign,@RequestBody無(wú)法繼承的解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
springboot集成schedule實(shí)現(xiàn)定時(shí)任務(wù)
在項(xiàng)目開(kāi)發(fā)過(guò)程中，我們經(jīng)常需要執(zhí)行具有周期性的任務(wù)。通過(guò)定時(shí)任務(wù)可以很好的幫助我們實(shí)現(xiàn)。本篇文章主要介紹了springboot集成schedule實(shí)現(xiàn)定時(shí)任務(wù)，感興趣的小伙伴們可以參考一下2018-05-05