时间:2021-05-19
复制代码 代码如下:
#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;
}
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
我们经常会在wps中制作树形图,你知道在wps里怎么制作树形图吗?对于新手来说还是有一定难度,怎么办?下面就让小编告诉你wps制作树形图的方法,希望对大家有
利用简单的树形视图实现,熟悉了组件的递归使用这是模拟的树形图数据letall={name:'all',children:{A:{name:'A',childre
本文实例为大家分享了Python生成树形图案的具体代码,供大家参考,具体内容如下先看一下效果,见下图。上面这颗大树是使用Python+Tkinter绘制的,主要
使用zTree插件实现树形图中,需要获取当前点击的父节点的子节点数的需求,使用treeNode.children获取子节点数据集合,使用length方法获取集合
本文实例讲述了JavaScript数据结构与算法之检索算法。分享给大家供大家参考,具体如下:javascript数据结构与算法---检索算法(顺序查找、最大最小