最小樹形圖模板朱劉算法分享
更新時間：2014年01月22日 15:21:11 作者：
這篇文章主要介紹了最小樹形圖模板朱劉算法，有需要的朋友可以參考一下
復(fù)制代碼 代碼如下:
/*
最小樹形圖圖模版-朱劉算法
模版說明：點標(biāo)號必須0-(N-1)
必須去除到自身的點（到自身的邊的邊權(quán)賦無限大）
*/
#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;//除了跟以外有點沒有入邊,則根無法到達(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)記每個環(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;//無環(huán)
for(int i=0;i<NV;i++) if(ID[i] == -1) {
ID[i] = cntnode ++;
}
//3.縮點,重新標(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)文章
這篇文章主要介紹了Java基于Base64實現(xiàn)編碼解碼圖片文件,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-03-03
這篇文章主要為大家詳細(xì)介紹了java簡單模仿win10計算器de，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
SpringBoot實現(xiàn)JWT token自動續(xù)期的示例代碼
本文主要介紹了SpringBoot實現(xiàn)JWT token自動續(xù)期的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
Java數(shù)組的特性_動力節(jié)點Java學(xué)院整理
數(shù)組是基本上所有語言都會有的一種數(shù)據(jù)類型，它表示一組相同類型的數(shù)據(jù)的集合，具有固定的長度，并且在內(nèi)存中占據(jù)連續(xù)的空間。在C，C++等語言中，數(shù)組的定義簡潔清晰，而在Java中確有一些會讓人迷惑的特性。本文就嘗試分析這些特性2017-04-04
今天小編就為大家分享一篇關(guān)于Java四種遍歷Map的方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
這篇文章主要介紹了java?字段值為null,不返回該字段的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
這篇文章主要給大家介紹了關(guān)于javaSE中數(shù)組的概念與使用的相關(guān)資料,數(shù)組在內(nèi)存中是一段連續(xù)的空間,空間的編號都是從0開始的,依次遞增,該編號稱為數(shù)組的下標(biāo),需要的朋友可以參考下2023-08-08
這篇文章主要介紹了SpringBoot之核心依賴和自動配置方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
模板消息是一種向用戶發(fā)送通知的服務(wù),廣泛用于訂單狀態(tài)更新、服務(wù)提醒等場景,下面,我將詳細(xì)介紹如何使用Java結(jié)合微信官方提供的API來實現(xiàn)模板消息的推送,感興趣的朋友跟隨小編一起看看吧2024-08-08
詳解SpringBoot 發(fā)布ApplicationEventPublisher和監(jiān)聽ApplicationEvent事
這篇文章主要介紹了詳解SpringBoot 發(fā)布ApplicationEventPublisher和監(jiān)聽ApplicationEvent事件，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-06-06