代码语言
.
CSharp
.
JS
Java
Asp.Net
C
MSSQL
PHP
Css
PLSQL
Python
Shell
EBS
ASP
Perl
ObjC
VB.Net
VBS
MYSQL
GO
Delphi
AS
DB2
Domino
Rails
ActionScript
Scala
代码分类
文件
系统
字符串
数据库
网络相关
图形/GUI
多媒体
算法
游戏
Jquery
Extjs
Android
HTML5
菜单
网页交互
WinForm
控件
企业应用
安全与加密
脚本/批处理
开放平台
其它
【
C/C++
】
最小生成树(kruskal邻接表形式)
作者:
智瑞
/ 发布于
2016/2/23
/
577
//无向图最小生成树,kruskal算法,邻接表形式,复杂度O(mlogm) //返回最小生成树的长度,传入图的大小n和邻接表list //可更改边权的类型,edge[][2]返回树的构造,用边集表示 //如果图不连通,则对各连通分支构造最小生成树,返回总长度 #include <string.h> #define MAXN 200 #define inf 1000000000 typedef double elem_t; struct edge_t{ int from,to; elem_t len; edge_t* next; }; #define _ufind_run(x) for(;p[t=x];x=p[x],p[t]=(p[x]?p[x]:x)) #define _run_both _ufind_run(i);_ufind_run(j) struct ufind{ int p[MAXN],t; void init(){memset(p,0,sizeof(p));} void set_friend(int i,int j){_run_both;p[i]=(i==j?0:j);} int is_friend(int i,int j){_run_both;return i==j&&i;} }; #define _cp(a,b) ((a).len<(b).len) struct heap_t{int a,b;elem_t len;}; struct minheap{ heap_t h[MAXN*MAXN]; int n,p,c; void init(){n=0;} void ins(heap_t e){ for (p=++n;p>1&&_cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1); h[p]=e; } int del(heap_t& e){ if (!n) return 0; for (e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[p]=h[c],p=c,c<<=1); h[p]=h[n--];return 1; } }; elem_t kruskal(int n,edge_t* list[],int edge[][2]){ ufind u;minheap h; edge_t* t;heap_t e; elem_t ret=0;int i,m=0; u.init(),h.init(); for (i=0;i<n;i++) for (t=list[i];t;t=t->next) if (i<t->to) e.a=i,e.b=t->to,e.len=t->len,h.ins(e); while (m<n-1&&h.del(e)) if (!u.is_friend(e.a+1,e.b+1)) edge[m][0]=e.a,edge[m][1]=e.b,ret+=e.len,u.set_friend(e.a+1,e.b+1); return ret; }
试试其它关键字
生成树
kruskal
邻接表
同语言下
.
C分鱼问题
.
链表
.
最大连续和
.
编码字符串
.
libiconv字符编码处理及判断字符串是否为utf8
.
一组数中两两二元组,差最大有几对,差最小呢?(数组
.
通过管道获取一个进程的执行状态
.
多关键字排序
.
字符串字典序排序
.
3元一次方程(牛顿迭代法求方程的根)
可能有用的
.
C#实现的html内容截取
.
List 切割成几份 工具类
.
SQL查询 多列合并成一行用逗号隔开
.
一行一行读取txt的内容
.
C#动态修改文件夹名称(FSO实现,不移动文件)
.
c# 移动文件或文件夹
.
c#图片添加水印
.
Java PDF转换成图片并输出给前台展示
.
网站后台修改图片尺寸代码
.
处理大图片在缩略图时的展示
智瑞
贡献的其它代码
(
12
)
.
60s倒计时
.
获取json对象的Key、value
.
置字体和字体颜色和字体样式
.
xml格式化输出函数
.
队列的基本操作,出队,入队,读取head
.
自动换行的流式布局
.
多线程访问数据库
.
分布式锁的创建
.
有向图强连通分支(bfs邻接阵形式)
.
最小生成树(kruskal邻接表形式)
Copyright © 2004 - 2024 dezai.cn. All Rights Reserved
站长博客
粤ICP备13059550号-3