最小树形图模板朱刘算法分享
发布时间:2023-11-07 07:04:38
标签:java,最小树形图,朱刘算法
/*
最小树形图图模版-朱刘算法
模版说明:点标号必须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;
}
0
投稿
猜你喜欢
- 一、什么是过滤器过滤器是对数据进行过滤,预处理过程,当我们访问网站时,有时候会发布一些敏感信息,发完以后有的会用*替代,还有就是登陆权限控制
- 使用JAVA工程管理越来越多的jar包,担心导错了,多导了,漏导了怎么办?换一个IDE项目后项目会不会出一堆BUG,看的头皮发麻?自己写的代
- 1.获取签名与模板进入阿里云平台,进入短信服务模块,在以下位置添加签名和模板(格式一定按照要求填写 审批的比较严格)2.编写模板与签名的枚举
- 1、什么是servlet异步请求Servlet 3.0 之前,一个普通 Servlet 的主要工作流程大致如下:(1)、Servlet 接收
- 一、什么是备忘录模式定义:在不破坏封闭的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态。这样以后就可将该对象恢复到原先保存的状态
- 一 前言redis在分布式应用十分广泛,本篇文章也是互联网面试的重点内容,读者至少需要知道为什么需要分布式锁,分布式锁的实现原理,分布式锁的
- 一、实验目的1. 掌握输入输出流的总体结构;2. 掌握流的概念;3. 掌握FileInputStream类、FileOutputStream
- SpringBootWeb开发回顾一下:springboot帮助我们配置了什么,能不能进行修改,能修改哪些,能否扩展?xxxAutoConf
- 好久没有做web了,JSON目前比较流行,闲得没事,所以动手试试将对象序列化为JSON字符(尽管DotNet Framework
- Android Studio 打包 jar 及 aar 包创建工程 New -> Module -> Library在gradl
- 相比于直线检测,直线拟合的最大特点是将所有数据只拟合出一条直线void fitLine( InputArray points, Output
- 本文实例为大家分享了java简单实现斗地主发牌的具体代码,供大家参考,具体内容如下问题:参考斗地主的游戏规则,完成一个发牌的功能(54张牌,
- 本文实例讲述了C++实现的链表类。分享给大家供大家参考。具体如下:#include <iostream>using namesp
- 背景最近好几个项目在运行过程中客户都提出文件上传大小的限制能否设置的大一些,用户经常需要上传好几个G的资料文件,如图纸,视频等,并且需要在上
- 打开首页,明显看到链接是https打头,https和http的通信协议差别,在于https安全性更高:http和https的差别很明显,二者
- Android 自动获取验证码的两种方式分别是BroadcastReceiver及ContentObserver,两种方式都需要进行注册、取
- 本文实例讲述了Android编程基于自定义View实现绚丽的圆形进度条功能。分享给大家供大家参考,具体如下:本文包含两个组件,首先上效果图:
- java项目中常用maven工具来进行工程管理,但经常遇到的一个问题是生成的jar包越来越大,编译一次工程越来越慢。怎么有效地去除冗余依赖,
- 前言在一个 Web 请求中,参数我们无非就是放在地址栏或者请求体中,个别请求可能放在请求头中。放在地址栏中,我们可以通过如下方式获取参数:S
- 1 依赖配置<parent> <groupId>org.springframework.b