最小树形图模板朱刘算法分享

代码如下:

/*
最小树形图图模版-朱刘算法
模版说明：点标号必须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)

相关推荐

  • 最小树形图模板朱刘算法分享

    复制代码 代码如下: /*最小树形图图模版-朱刘算法模版说明:点标号必须0-(N-1)   必须去除到自身的点(到自身的边的边权赋无限大)*/#define M 109#define type intconst 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

  • 70行Java代码实现深度神经网络算法分享

    70行Java代码实现深度神经网络算法分享

    对于现在流行的深度学习,保持学习精神是必要的--程序员尤其是架构师永远都要对核心技术和关键算法保持关注和敏感,必要时要动手写一写掌握下来,先不用关心什么时候用到--用不用是政治问题,会不会写是技术问题,就像军人不关心打不打的问题,而要关心如何打赢的问题. 程序员如何学习机器学习 对程序员来说,机器学习是有一定门槛的(这个门槛也是其核心竞争力),相信很多人在学习机器学习时都会为满是数学公式的英文论文而头疼,甚至可能知难而退.但实际上机器学习算法落地程序并不难写,下面是70行代码实现的反向多层(BP

  • C++ STL中的常用遍历算法分享

    目录 1.for_each 功能描述 函数原型 2.transform 功能描述 函数原型 1.for_each 功能描述 实现容器遍历 函数原型 for_each(itertor beg,iterator end,_func);//遍历算法 遍历容器元素//beg 开始迭代器//end 结束迭代器//_func函数或者函数对象 代码 #include <iostream> using namespace std; #include <vector> #include <al

  • PHP实现转盘抽奖算法分享

    本文实例为大家分享了PHP实现转盘抽奖算法的具体代码,供大家参考,具体内容如下 流程: 1.拼装奖项数组 2.计算概率 3.返回中奖情况 代码如下: 中奖概率 ' v ' 可以在后台设置,传到此方法中,注意传整数 function get_gift(){ //拼装奖项数组 // 奖项id,奖品,概率 $prize_arr = array( '0' => array('id'=>1,'prize'=>'平板电脑','v'=>0), '1' => array('id'=>2

  • Java中打乱一个数组的2种公平算法分享

    公平算法,打乱数组 这是前几天面试的时候遇见的一道题目,看到这个题首先想到了洗牌程序: 方法一:洗牌程序原理 在java.util包中的Collections类中的 shuffle方法,现在手工实现以下代码如下: package test.ms; import java.util.Random; public class Redistribute2 { public static void main(String[] args) { //define the array int[] s = {1

  • 史上最全的java随机数生成算法分享

    史上最全的java随机数生成算法分享

    复制代码 代码如下: String password = RandomUtil.generateString(10); 源码如下: 复制代码 代码如下: package com.javaniu.core.util;import java.util.Random;public class RandomUtil { public static final String ALLCHAR = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRS

  • PHP将URL转换成短网址的算法分享

    前言 短网址服务,可能很多朋友都已经不再陌生,现在大部分微博.手机邮件提醒等地方已经有很多应用模式了,并占据了一定的市场.估计很多朋友现在也正在使用. 短链接的好处: 1.内容需要: 2.用户友好: 3.便于管理. 下面是用PHP实现短网址转换的算法,代码如下: PHP <?php //短网址生成算法 class ShortUrl { //字符表 public static $charset = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghij

  • JavaScript实现的一个计算数字步数的算法分享

    这两天看了下某位大神的github,知道他对算法比较感兴趣,看了其中的一个计算数字的步数算法,感觉这个有点意思,所以就自己实现了一个. 算法描述与实现原理 给出一个整型数字,统计出有多少种走法可以到达目标,比如一个数字4,可以有下面几种走法 复制代码 代码如下: [ 1, 3 ]         [ 4 ]     [ 1, 1, 2 ]         [ 2, 2 ]     [ 1, 1, 1, 1 ] 其实通过上面的组合可以得出下面的结论. 1.先列出所有项是1的组合 2.依次从左到右项

  • ASP.NET加密解密算法分享

    #region DES加密解密 /// <summary> /// DES加密 /// </summary> /// <param name="strSource">待加密字串</param> /// <param name="key">32位Key值</param> /// <returns>加密后的字符串</returns> public string DESEncr

  • Linux静态链接库使用类模板的快速排序算法

    快速排序的本质是从数组中选一个参考值ref,比该参考值的大的,将其放在ref的右边,比ref小的放在左边,然后不断的对两边重复执行该动作 我们先列出来快速排序的步骤: 1.从数组中选一个参考值ref,比该参考值的大的,将其放在ref的右边, 上面的动作将数组划分为两部分: A ref B A是比ref小的数组元素集合,它仍然是数组,B是比ref大的元素集合,它也仍然是数组 2.在对ref左右两边的元素重复上述动作,直到A和B都只剩下一个元素,那么排序就算完成了. 重点是如何分别选出来两个集合A和

随机推荐