最小生成树与最小树形图 最小生成树 最小树形图
从无向图的角度讲,对于一个联通的无向图,我们可以构造出这个无向图的一棵生成树.形式化地说,一棵给定无向图$G=(V,E)$的生成树$S$是一个图$(V,E')$,满足
1) $S$联通.
2) $S$中不存在环.
我们可以定义边的权值$w(E)$,一般来说,$w(E)$的值相对边是独立的(互不影响)的.一棵生成树的权值$w(T)$就是它的边的权值和.最小生成树,就是使$w(T)$最小的生成树$Tin g(G)$.$g(G)$是$G$生成树的集合.)
最小生成树一般用著名的Kruskal算法求.这个算法很优美,写起来也很方便.
但是这里要介绍一个不常见但是非常好用的新算法,对最小树形图的算法也很有启发.
Borůvka 算法
这个算法的基本思想是每次寻找可以放入最小生成树的边.算法基本步骤:
如果没有生成最小生成树:
-> 1 遍历所有边,找出点的最小外联边
-> 2 将这些外联边加入最小生成树,形成一些联通分量
-> 3 对于每个新形成的联通分量缩点
时间复杂度分析
每次对于一个点都会至少找出另外一个点与它组成联通块,最坏情况需要迭代$log_2{|V|}$次,每次$O(E)$,因此时间复杂度上限$O(Elog_2{V})$,对于随机图会更快些.这里假设并查集查找与合并的时间复杂度$O(1)$.
最小树形图
讲最小生成树的目的当然是为了讲最小树形图.
对于一个有向图$G=(V,E)$,我们可以定义出它的树形图集合$g(G)$,其中的每一个元素$Sin g(G)=(V,E')$满足:
1) $S$半联通(单向联通).
2) $S$中没有环.
可以看出这是一棵有根树.
如图中的橙色边标出了这个图的一个树形图.
补个约大爷版的代码(不是约大爷写的...对着约大爷的代码打的...)
#include <cstdio>
#include <algorithm>
#include <set>
#define fon(i,s) for(int i=0;i<s; ++i)
#define fone(i,s) for(int i=0;i<=s;++i)
#define fox(i,f,t) for(int i=f;i<t; ++i)
#define foxe(i,f,t) for(int i=f;i<=t;++i)
#define fdn(i,s) for(int i=s;i; --i)
#define fdne(i,s) for(int i=s;~i; --i)
#define fdx(i,f,t) for(int i=f;i>t; --i)
#define fdxe(i,f,t) for(int i=f;i>=t;--i)
struct Info{
int S,C,U;
Info* c[2];
inline Info(){}
inline Info(int CC){ c[0]=0,c[1]=0,S=0,U=0,C=CC; }
inline Info(bool ibp,Info* c0,Info* c1){
S=(ibp<<1)-1,c[0]=c0,c[1]=c1,U=0;
C=c[0]->C+S*c[1]->C;
}
inline Info* operator()(int CC){ c[0]=0,c[1]=0,S=0,U=0,C=CC;return this; }
inline Info* operator()(bool ibp,Info* c0,Info* c1){
S=(ibp<<1)-1,c[0]=c0,c[1]=c1,U=0;
C=c[0]->C+S*c[1]->C;
return this;
}
inline void pick(){++U;}
inline void inhr(){if(S){c[0]->U+=U,c[1]->U+=S*U,U=0;}}
} NIL(0);
#define VM 500001
struct _uvec{
Info* a[VM];
int l,p;
inline void push_back(Info* b){a[l++]=b;}
inline Info* operator[](int n){return a[n];}
inline Info** operator+(int n){return a+n;}
inline int riter(){return p--;}
inline void startRIterSession(){p=l;}
inline Info* iterP(){return a[p];}
} dr;
Info IS[VM];
int ISL;
#define new_Info IS[ISL++]
inline Info* Add(Info* a,Info* b){
if(a==&NIL) return b;
if(b==&NIL) return a;
Info* n=new_Info(1,a,b);
dr.push_back(n);
return n;
}
inline Info* Sub(Info* a,Info* b){
if(b==&NIL) return a;
Info* n=new_Info(0,a,b);
dr.push_back(n);
return n;
}
struct Leftist{
Leftist* s[2];
Info *vf,*Msk;
int vs,dist;
inline Leftist(Info *v=&NIL,int sx=0){ s[0]=NULL,s[1]=NULL,dist=1,vf=v,vs=sx,Msk=&NIL; }
inline Leftist* operator()(Info *v=&NIL,int sx=0){ s[0]=NULL,s[1]=NULL,dist=1,vf=v,vs=sx,Msk=&NIL;return this;}
inline int key(){
return vf->C;
}
};
inline int dist(Leftist* x){return (x)?x->dist:0;}
inline void Push(Leftist* x){//Info pushdown
if(x->s[0]) x->s[0]->Msk=Add(x->s[0]->Msk,x->Msk);
if(x->s[1]) x->s[1]->Msk=Add(x->s[1]->Msk,x->Msk);
x->vf=Sub(x->vf,x->Msk),x->Msk=&NIL;
}
Leftist* Merge(Leftist* l,Leftist* r){
if(l==NULL) return r;
if(r==NULL) return l;
Push(l),Push(r);
if(l->key()>r->key()) std::swap(l,r);
l->s[1]=Merge(l->s[1],r);
if(dist(l->s[0])<dist(l->s[1])) std::swap(l->s[0],l->s[1]);
l->dist=dist(l->s[1])+1;
return l;
}
Leftist* Extract(Leftist* &x){
Push(x);Leftist* ret=x;
x=Merge(x->s[0],x->s[1]);
return ret;
}
#define MAXN 100012
#define MAXM MAXN
int N,M,hl;
Leftist *heap[MAXN],_h[VM];
#define _L _h[hl++]
struct djset{
int f[MAXN];
inline void Init(){
int u=1+(N<<2);
fone(i,u) f[i<<2]=-1,f[i<<2|1]=-1,f[i<<2|2]=-1,f[i<<2|3]=-1;
}
int find(int x){return ~f[x]?(f[x]=find(f[x])):x;}
inline bool uni(int x,int y){
x=find(x),y=find(y);
if(x==y) return false;
return (f[y]=x);
}
inline bool cnx(int x,int y){
return find(x)==find(y);
}
} weak,strong;
std::set<int> activeStrong;//I don't want to write a set implementation T^T
inline void Join(int u,int v){
strong.uni(u,v);
heap[u]=Merge(heap[u],heap[v]),heap[v]=NULL,activeStrong.insert(u);
}
Info baseInfo[MAXM],*prevCost[MAXN];
int prev[MAXN],Ans;
inline bool Connected(){
foxe(i,1,N) if(!weak.cnx(1,i)) return 0;
return 1;
}
struct _veci{
int s[VM],sl;
inline void push_back(int n){s[sl++]=n;}
inline void clear(){sl=0;}
inline int back(){return s[sl-1];}
inline int operator[](int n){return s[n];}
inline int size(){return sl;}
} LIZ;
int main(){
scanf("%d%d",&N,&M);
foxe(i,1,N) heap[i]=NULL;
foxe(i,1,M){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
baseInfo[i](w);
if(v==1) continue;
heap[v]=Merge(heap[v],_L(baseInfo+i,u));
}
activeStrong.clear();
foxe(i,2,N) activeStrong.insert(i);
weak.Init(),strong.Init(),Ans=0;
while(activeStrong.size()){
int s0=*activeStrong.begin();
if(heap[s0]==NULL){ activeStrong.erase(s0);continue; }
Leftist* pdi=Extract(heap[s0]);
int S=strong.find(pdi->vs);
if(S==s0) continue;
if(!weak.cnx(pdi->vs,s0)){
prev[s0]=pdi->vs,prevCost[s0]=pdi->vf,Ans+=pdi->vf->C,pdi->vf->pick();
weak.uni(pdi->vs,s0);
activeStrong.erase(s0);
continue;
}
LIZ.clear();
LIZ.push_back(strong.find(pdi->vs));
while(LIZ.back()!=s0) LIZ.push_back(strong.find(LIZ.back()));
Ans+=pdi->vf->C;
pdi->vf->pick();
if(heap[s0]) heap[s0]->Msk=Add(heap[s0]->Msk,pdi->vf);
int SZ=LIZ.size();
fon(i,SZ-1) if(heap[LIZ[i]]) heap[LIZ[i]]->Msk=Add(heap[LIZ[i]]->Msk,prevCost[LIZ[i]]);
fon(i,SZ-1) Join(s0,LIZ[i]);
}
if(!Connected()){ printf("-1
"); return 0; }
printf("%d
",Ans);
LIZ.clear(),dr.startRIterSession();
while(dr.riter()) dr.iterP()->inhr();
foxe(i,1,M) if((baseInfo[i].U)&&(baseInfo[i].C)) LIZ.push_back(i);
fon(i,Ans) printf("%d%s",LIZ[i],(i==Ans-1)?"
":" ");
return 0;
}