图论—最小生成树模板

《图论—最小生成树模板》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3图论—最小生成树3.1最小生成树(kruskal邻接表)//无向图最小生成树,kruskal算法,邻接表形式,复杂度O(mlogm)//返回最小生成树的长度,传入图的大小n和邻接表list//可更改边权的类型,edge[][2]返回树的构造,用边集表示//如果图不连通,则对各连通分支构造最小生成树,返回总长度#include#defineMAXN200#defineinf1000000000typedefdoubleelem_t;structedge_t{intfrom,to;elem_tlen;edge_t*next;};#define_ufind_run(x)for(

2、;p[t=x];x=p[x],p[t]=(p[x]?p[x]:x))#define_run_both_ufind_run(i);_ufind_run(j)structufind{intp[MAXN],t;voidinit(){memset(p,0,sizeof(p));}voidset_friend(inti,intj){_run_both;p[i]=(i==j?0:j);}intis_friend(inti,intj){_run_both;returni==j&&i;}};#define_cp(a,b)((a).len<(b).len)structheap_t{inta,b;elem_tle

3、n;};structminheap{heap_th[MAXN*MAXN];intn,p,c;voidinit(){n=0;}voidins(heap_te){for(p=++n;p>1&&_cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1);h[p]=e;}intdel(heap_t&e){if(!n)return0;for(e=h[p=1],c=2;c

4、t*list[],intedge[][2]){ufindu;minheaph;edge_t*t;heap_te;elem_tret=0;inti,m=0;u.init(),h.init();for(i=0;inext)if(ito)e.a=i,e.b=t->to,e.len=t->len,h.ins(e);while(m

5、+1);returnret;}3.2最小生成树(kruskal正向表)//无向图最小生成树,kruskal算法,正向表形式,复杂度O(mlogm)//返回最小生成树的长度,传入图的大小n和正向表list,buf//可更改边权的类型,edge[][2]返回树的构造,用边集表示//如果图不连通,则对各连通分支构造最小生成树,返回总长度#include#defineMAXN200#defineinf1000000000typedefdoubleelem_t;structedge_t{intto;elem_tlen;};#define_ufind_run(x)for(;p[t=x]

6、;x=p[x],p[t]=(p[x]?p[x]:x))#define_run_both_ufind_run(i);_ufind_run(j)structufind{intp[MAXN],t;voidinit(){memset(p,0,sizeof(p));}voidset_friend(inti,intj){_run_both;p[i]=(i==j?0:j);}intis_friend(inti,intj){_run_both;returni==j&&i;}};#define_cp(a,b)((a).len<(b).len)structheap_t{inta,b;elem_tlen;};str

7、uctminheap{heap_th[MAXN*MAXN];intn,p,c;voidinit(){n=0;}voidins(heap_te){for(p=++n;p>1&&_cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1);h[p]=e;}intdel(heap_t&e){if(!n)return0;for(e=h[p=1],c=2;c