最小树形图模板朱刘算法分享
程序员文章站
2024-03-31 11:25:34
复制代码 代码如下:/*最小树形图图模版-朱刘算法模版说明:点标号必须0-(n-1) 必须去除到自身的点(到自身的边的边权赋无限大)*/#defin...
复制代码 代码如下:
/*
最小树形图图模版-朱刘算法
模版说明:点标号必须0-(n-1)
必须去除到自身的点(到自身的边的边权赋无限大)
*/
#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;//除了跟以外有点没有入边,则根无法到达它
}
//2.找环
int cntnode = 0;
memset(id,-1,sizeof(id));
memset(vis,-1,sizeof(vis));
in[root] = 0;
for(int i=0;i<nv;i++) {//标记每个环
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;//无环
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 = cntnode;
root = id[root];
}
return ret;
}