生成树总结

发表于 分类于 ， ， 阅读次数： 44 本文字数： 19k 阅读时长 ≈ 17 分钟

生成树

一个无向图的生成树指的是从图中选若干边构成边集，全部点构成点集，使得这个边集加上点集恰好是一棵树。

生成树计数

一个无向无权图(允许重边不允许自环)的邻接矩阵为g，显然这是一个对称矩阵，g[u][v]代表边(u,v)的重数，即若存在一条边(u,v)则g[u][v]的值为1，若存在k条，则g[u][v]的值为k。
一个无向无权图(允许重边不允许自环)的度数矩阵为deg，显然这是一个对角矩阵，deg[u][u]代表点u的度数。
一个无向无权图(允许重边不允许自环)的基尔霍夫矩阵(拉普拉斯矩阵)为hoff，是度数矩阵减去邻接矩阵。
矩阵树定理说一个无向图的生成树的个数刚好等于基尔霍夫矩阵的行列式的任意n-1阶主子式(代数余子式)的行列式的绝对值。
生成树计数复杂度O(V3+E)=O(V3)
黑暗前的幻想乡
我们利用矩阵树定理就能轻松解决
黑暗前的幻想乡代码
p4336view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

/*
 *
 * 矩阵树定理
 * 基尔霍夫矩阵定义为度数矩阵减去邻接矩阵
 * 生成树的个数等于基尔霍夫矩阵的任意一个代数余子式的行列式的值的绝对值
 * 完全图的生成树的个数是pow(n,n-2)
 *
 *
 * p4336
 * 容斥+矩阵树定理
 *
 *
 * */

const int V=20,p=1e9+7;
typedef long long ll;
ll qpow(ll a,ll b){ll s=1;for(;b;b>>=1,a=a*a%p)if(b&1)s=s*a%p;return s;}
int hoff[V][V];// memset(hoff,0,sizeof(hoff));
void addedge(int u,int v){hoff[u][u]++,hoff[v][v]++,hoff[u][v]--,hoff[v][u]--;}
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
static int det(int m[V][V],int n,int p){// 可以计算任意行列式的值 a[1..n][1..n]
    int r=1;
    rep(i,1,n) rep(j,1,n) m[i][j]=(m[i][j]%p+p)%p;
    rep(i,1,n) rep(j,i+1,n) {//枚举行i，去消掉行j 目的是将他变成上三角
        int &u=m[i][i],&v=m[j][i],a=1,b=0,c=0,d=1;
        while(v){// x=m[i][i],y=m[j][i],则u=ax+by&&v=cx+dy)
            int k=p-u/v;
            a=(a+1ll*k*c)%p,b=(b+1ll*k*d)%p,u=(u+1ll*k*v)%p;//此行消元
            swap(u,v),swap(a,c),swap(b,d),r=-r;//行互换 行列式值变为相反数
        }
        rep(k,i+1,n) {//消元
            int x=m[i][k],y=m[j][k];
            m[i][k]=(1ll*a*x+1ll*b*y)%p;
            m[j][k]=(1ll*c*x+1ll*d*y)%p;
        }
    }
    rep(i,1,n) r=1ll*r*m[i][i]%p;
    return (r+p)%p;
}

typedef pair<int,int>pii;
int read(){int a;scanf("%d",&a);return a;}
int main(){
    vector<pii> v[20];
    int n=read();
    rep(i,1,n-1) for(int x=read();x>=1;--x) v[i].emplace_back(read(),read());
    int up=(1<<(n-1))-1,ans=0;
    rep(i,0,up){
        rep(x,1,n)rep(y,1,n) hoff[x][y]=0;
        for(int j=i;j;j&=j-1) for(pii x:v[__builtin_ffs(j)])addedge(x.first,x.second);
        if(__builtin_parity(i^up)&1) ans=(ans+p-det(hoff,n-1,p))%p;
        else ans=(ans+det(hoff,n-1,p))%p;
    }
    cout<<ans<<endl;
}

最小生成树

有一个无向带权图，每条边有权xi，需要求出一个生成树T，并最小化∑i∈Txi kruskal算法：贪心从小到大枚举边合并森林即可。这里就不证明此算法了。
最小生成树复杂度O(V+ElgE)=O(ElgE)
最小生成树
最小生成树代码
p3366view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

const int N=5000+5;
int f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

struct edge{int u,v,w;};
edge g[200000+10];

int read(){int x;scanf("%d",&x);return x;}
int main(){
    //最小生成树 复杂度O(mlgm)
    //n为点数,m为边数，后面m行u->v边权w 保证联通且存在最小生成树
    int n=read(),m=read();
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) g[i].u=read(),g[i].v=read(),g[i].w=read();
    sort(g+1,g+1+m,[](edge l,edge r){return l.w<r.w;});
    int ans=0;
    for(int i=1;i<=m;i++) {
        if(find(g[i].u)!=find(g[i].v)){
            f[find(g[i].u)]=find(g[i].v);
            ans+=g[i].w;
        }
    }
    cout<<ans<<endl;
}

最小生成树计数

由于最小生成树各自边权构成的多重集合是一样的，并且易证不同的边权对最小生成树的影响是独立的，所以我们可以通过将边按照边权分类，分别求出每一种边权各自对联通块的贡献，然后利用计数的乘法原理合并即可。我们需要先求出任意一个最小生成树，当我们对某一种边权进行讨论的时候，我们需要将这个生成树中这一边权的边全删掉，然后对剩余联通块进行缩点并重新编号，将待选集合中的边映射到联通块间的边，并去掉自环。这样以后待选集合中的边的边权就相等了。这时我们可以借助矩阵树定理来求解。
最小生成树计数复杂度O(ElgE+V3)=O(V3)
最小生成树计数
最小生成树计数代码
p4208view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

/*
 *
 * 矩阵树定理
 * 基尔霍夫矩阵定义为度数矩阵减去邻接矩阵
 * 生成树的个数等于基尔霍夫矩阵的任意一个代数余子式的行列式的值的绝对值
 * 完全图的生成树的个数是pow(n,n-2)
 *
 *
 * p4208
 * 最小生成树计数
 *
 *
 * */
typedef long long ll;
#define rep(i,j,k) for(int i=(j);i<=int(k);++i)
#define SZ(x) int(x.size())

const int N=1e5;
int f[N];
inline int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

vector<int>disc;
int getid(int x){return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;}
ll qpow(ll a,ll b,ll p){ll s=1;for(;b;b>>=1,a=a*a%p)if(b&1)s=s*a%p;return s;}
struct mst{
    struct sedge{int u,v,w;};
    static const int V=105;
    int hoff[V][V];// memset(hoff,0,sizeof(hoff));
    void addedge(int u,int v){hoff[u][u]++,hoff[v][v]++,hoff[u][v]--,hoff[v][u]--;}
    static int det(int m[V][V],int n,int p){// 可以计算任意行列式的值 a[1..n][1..n]
        int r=1;
        rep(i,1,n) rep(j,1,n) m[i][j]=(m[i][j]%p+p)%p;
        rep(i,1,n) rep(j,i+1,n) {//枚举行i，去消掉行j 目的是将他变成上三角
                int &u=m[i][i],&v=m[j][i],a=1,b=0,c=0,d=1;
                while(v){// x=m[i][i],y=m[j][i],则u=ax+by&&v=cx+dy)
                    int k=p-u/v;
                    a=(a+1ll*k*c)%p,b=(b+1ll*k*d)%p,u=(u+1ll*k*v)%p;//此行消元
                    swap(u,v),swap(a,c),swap(b,d),r=-r;//行互换 行列式值变为相反数
                }
                rep(k,i+1,n) {//为了处理非质数的消元方案，这里采取了这种不明智的方案，导致常数增大了一倍
                    int x=m[i][k],y=m[j][k];
                    m[i][k]=(1ll*a*x+1ll*b*y)%p;
                    m[j][k]=(1ll*c*x+1ll*d*y)%p;
                }
            }
        rep(i,1,n) r=1ll*r*m[i][i]%p;
        return (r+p)%p;
    }
    int countmst(sedge*edge,int n,int m,int p){// 1..n
        sort(edge+1,edge+1+m,[](sedge&a,sedge&b){return a.w<b.w;});
        rep(i,1,n) f[i]=i;
        vector<int>used;
        rep(i,1,m) {
            if(find(edge[i].u)!=find(edge[i].v)){
                f[find(edge[i].u)]=find(edge[i].v);
                used.push_back(i);
            }
        }
        if(SZ(used)!=n-1) return 0;//无树
        int ans=1;
        for(int l=1,r=0;l<=m;l=r+1){
            while(r+1<=m&&edge[r+1].w==edge[l].w) ++r;
            rep(i,1,n) f[i]=i;// O(n*n)
            for(int i:used) if(i<l||i>r) f[find(edge[i].u)]=find(edge[i].v);//O(n*n)
            disc.clear();
            rep(i,l,r) if(find(edge[i].u)!=find(edge[i].v)) {//准备离散化
                    disc.push_back(find(edge[i].u));
                    disc.push_back(find(edge[i].v));
                }
            sort(disc.begin(),disc.end());
            disc.erase(unique(disc.begin(),disc.end()),disc.end());
            rep(i,1,SZ(disc))rep(j,1,SZ(disc))hoff[i][j]=0;
            rep(i,l,r) if(find(edge[i].u)!=find(edge[i].v)) { //利用矩阵树定理合并
                addedge(getid(find(edge[i].u)),getid(find(edge[i].v)));
            }
            ans=1ll*ans*det(hoff,SZ(disc)-1,p)%p;
        }
        return ans;
    }
}g;

int read(){int a;scanf("%d",&a);return a;}
int main(){
    int n=read(),m=read();
    vector<mst::sedge>edge;
    rep(i,1,m) {
        int u=read(),v=read(),w=read();
        edge.push_back(mst::sedge{u,v,w});
    }
    cout<<g.countmst(edge.data()-1,n,m,31011)<<endl;
}

严格次小生成树

严格次小生成树和最小生成树的边权多重集合中只有一个边权不一样，这样我们就有了一个简单的算法，先求出任意一个最小生成树，然后枚举没有被选中为构建最小生成树的边，假设这个边为(u,v,w1)，我们在最小生成树上求出点u到点v这条路径上的最大边权w2和严格次大边权w3，若w1=w2则我们用此边换掉次大边，若w1>w2则我们用此边换掉最大边，这样我们最终能得到很多非最小生成树，从中选出最小的那个，他就是次小生成树,这个过程需要维护树上的路径信息，有算法都可以树剖、树上倍增、lct等等，我们这里使用树上倍增的办法来解决。
严格次小生成树时间复杂度O(ElgE+ElnV)=O(ElgE)
严格次小生成树
严格次小生成树代码
p4180view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define rep(i,j,k) for(int i=j;i<=int(k);++i)
#define per(i,j,k) for(int i=j;i>=int(k);--i)
#define repe(i,u) for(int i=head[u];~i;i=nex[i])
int lg[1<<18];// rep(i,2,1<<18) lg[i]=lg[i>>1]+1;
struct tree{
    static const int V=1e5+5,E=2*V;
    int head[V],n;
    int to[E],nex[E],ew[E],m,tot;
    void addedge1(int u,int v,int w) {to[++tot]=v,nex[tot]=head[u],ew[tot]=w,head[u]=tot;}
    void addedge(int u,int v,int w){addedge1(u,v,w),addedge1(v,u,w);}
    void ini(int _n){tot=-1; n=_n; rep(i,1,n)head[i]=-1;}
    void upd(int*x,int*y){// max
        if(x[1]==y[1]) x[0]=max(x[0],y[0]);
        else if(x[1]>y[1]) x[0]=y[1];
        else x[0]=x[1],x[1]=y[1];
    }
    void upd(int*x,int*y,int*z){upd(x,y),upd(x,z);}
    int f[V][21],pw[V][21][2],dep[V];
    void dfs(int u,int father,int w=0){
        dep[u]=dep[father]+1;
        f[u][0]=father;
        pw[u][0][0]=0;
        pw[u][0][1]=w;
        rep(i,1,20) {
            f[u][i]=f[f[u][i-1]][i-1]; // assert(f[0][i]=0);
            upd(pw[u][i],pw[u][i-1],pw[f[u][i-1]][i-1]);
        }
        repe(i,u)if(to[i]!=father)dfs(to[i],u,ew[i]);
    }
    pii getbigedge(int x,int y){
        int res[2]={0,0};
        if(dep[x]<dep[y]) swap(x,y);
        while(dep[x]>dep[y]) {
            upd(res,pw[x][lg[dep[x]-dep[y]]]);
            x=f[x][lg[dep[x]-dep[y]]];// 取下整
        }if(x==y)return pii(res[0],res[1]);
        per(i,lg[dep[x]-1],0) if(f[x][i]!=f[y][i]) {
                upd(res,pw[x][i],pw[y][i]);
                x=f[x][i],y=f[y][i];
            }
        upd(res,pw[x][0],pw[y][0]);
        return pii(res[0],res[1]);
    }
};

struct secondtmst{
    static const int N=1e5+5;
    int f[N];
    int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
    struct edge{int u,v,w;};

    long long kruskal(int n, vector<edge> &g, tree &t) {
        vector<edge> nmst;
        long long res=0;
        int add=1e9;//设置边权最大值
        rep(i,1,n) f[i]=i;
        sort(g.begin(),g.end(),[](edge l,edge r){return l.w<r.w;});
        t.ini(n);
        for(edge e:g) {
            if(find(e.u)!=find(e.v)) {
                f[find(e.u)]=find(e.v);
                t.addedge(e.u,e.v,e.w);
                res+=e.w;
            }else nmst.push_back(e);
        }
        t.dfs(1,0);

        for(edge e:nmst) {
            pii tmp=t.getbigedge(e.u,e.v);
            if(tmp.second!=e.w) add=min(add,e.w-tmp.second);
            if(tmp.first!=e.w) add=min(add,e.w-tmp.first);
        }
        return res+add;
    }
};

tree t;
secondtmst mst;

int read(){int x;scanf("%d",&x);return x;}
int main(){
    rep(i,2,1<<18) lg[i]=lg[i>>1]+1;
    int n=read(),m=read();// n<1e5个点 m<3e5边 0<=w<=1e9
    vector<secondtmst::edge>g(m);
    rep(i,0,m-1) g[i].u=read(),g[i].v=read(),g[i].w=read();
    cout<<mst.kruskal(n,g,t)<<endl;
}

最小乘积生成树

有一个无向带权图(权为正数)，每条边有权xi和权yi，需要求出一个生成树T，记X=∑i∈Txi,Y=∑i∈Tyi,要求最小化乘积XY
我们假设已经求出了所有生成树，他们的权为(Xi,Yi)我们把这个二元组看做二维平面上的点，则最小乘积生成树一定在凸包上。进一步分析，整个凸包都在第一象限，那么我们可以锁定出两个点了，他们一定在凸包上。分别求出最小的Xi对映点A，和最小的Yi对映点B，那么答案就在AB左下方，我们求出一个点C，若能让叉积AC∗AB最大且为正数，则C一定也在凸包上。我们递归处理AC和CB即可。凸包上的点期望为lg级别。
最小乘积生成树复杂度O(ElgElg(V!))=O(ElgElgV)
最小乘积生成树
最小乘积生成树代码
p5540view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

const int N=5000+5;
int f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

struct edge{int u,v,w,x,y;};
edge g[200000+10];
//最小乘积生成树 O(mlgmsqrt(lgn!))=O(mlgmlgn) //https://www.luogu.org/problem/P5540
void kruskal(int n,int m,int&x,int&y){
    x=y=0;
    for(int i=1;i<=n;++i) f[i]=i;
    sort(g+1,g+1+m,[](edge l,edge r){return l.w<r.w;});
    for(int i=1;i<=m;++i) {
        if(find(g[i].u)!=find(g[i].v)){
            f[find(g[i].u)]=find(g[i].v);
            x+=g[i].x,y+=g[i].y;
        }
    }
}

int ansx,ansy;
void update(int x,int y){
    if(x*y<ansx*ansy) ansx=x,ansy=y;
    else if(x*y==ansx*ansy&&x<ansx) ansx=x,ansy=y;
}
void solve(int n,int m,int x1,int y1,int x2,int y2){
    int x3,y3;
    for(int i=1;i<=m;++i) g[i].w=g[i].y*(x2-x1)+g[i].x*(y1-y2);
    kruskal(n,m,x3,y3);
    update(x3,y3);
    if((x2-x1)*(y3-y1)>=(x3-x1)*(y2-y1)) return;
    solve(n,m,x1,y1,x3,y3);
    solve(n,m,x3,y3,x2,y2);
}

int read(){int x;scanf("%d",&x);return x;}
int main(){
    //n为点数,m为边数，后面m行u->v边权(x,y) 保证联通且存在最小生成树
    int n=read(),m=read();
    for(int i=1;i<=m;++i) g[i].u=read()+1,g[i].v=read()+1,g[i].x=read(),g[i].y=read();
    int x1,y1,x2,y2;
    for(int i=1;i<=m;++i) g[i].w=g[i].x;
    kruskal(n,m,x1,y1);
    for(int i=1;i<=m;++i) g[i].w=g[i].y;
    kruskal(n,m,x2,y2);
    ansx=x1,ansy=y1;
    update(x2,y2);
    solve(n,m,x1,y1,x2,y2);
    cout<<ansx<<" "<<ansy<<endl;
}

最小差值生成树

有一个无向带权图，每条边有权xi，需要求出一个生成树T，让T的最大边权和最小边权的差值尽可能小。
我们对边集排序后，等价于求最短的一段区间，这个区间内部的边能够生成一棵树，这种连通性维护的问题，直接使用lct就可以了，
最小差值生成树时间复杂度O(ElgE+Elg(E+V))=O(ElgE)
最小差值生成树
最小差值生成树代码
p4234view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;

//仅仅维护图联通的lct tle可能因为自环
struct graphlct{
    static const int V=5e4+5,E=2e5+5;
    static const int N=V+E;//拆点
    int X[N],Y[N],W[N],n,m;//预先传入的参数
    int c[N][2],f[N],t[N],s[N],rev[N],val[N];// t->times s->stack
    set<int>e;
    void ini(){// X是边起点从1开始，Y是终点从1开始，R是删除的顺序，越小越先删除 edgenums维护边的条数
        e.clear();
        for(int i=0;i<=n;i++)c[i][0]=c[i][1]=f[i]=rev[i]=0,t[i]=i,val[i]=2e9;
        for(int i=n+1;i<=n+m;i++)c[i][0]=c[i][1]=f[i]=rev[i]=0,t[i]=i,val[i]=W[i-n];
    }
    inline void pushup(int x){
        t[x]=x;
        if(val[t[c[x][0]]]<val[t[x]]) t[x]=t[c[x][0]];
        if(val[t[c[x][1]]]<val[t[x]]) t[x]=t[c[x][1]];
    }
    inline void pushdown(int x){
        int l=c[x][0],r=c[x][1];
        if(rev[x]){
            rev[l]^=1;rev[r]^=1;rev[x]^=1;
            swap(c[x][0],c[x][1]);
        }
    }
    inline bool isroot(int x){return c[f[x]][0]!=x&&c[f[x]][1]!=x;}
    inline void rotate(int x){
        int y=f[x],z=f[y],xis=c[y][1]==x,yis=c[z][1]==y;//
        if(!isroot(y)) c[z][yis]=x;//son
        f[x]=z;f[y]=x;f[c[x][xis^1]]=y;//father
        c[y][xis]=c[x][xis^1];c[x][xis^1]=y;//son
        pushup(y);
    }
    inline void splay(int x){
        s[s[0]=1]=x;//init stack
        for(int i=x;!isroot(i);i=f[i])s[++s[0]]=f[i];//update stack
        for(int i=s[0];i;i--)pushdown(s[i]);//pushroad
        while(!isroot(x)){
            int y=f[x],z=f[y];
            if(!isroot(y)) (c[y][0]==x)^(c[z][0]==y)?rotate(y):rotate(x);
            rotate(x);
        }pushup(x);
    }
    inline void access(int x){for(int i=0; x; i=x, x=f[x])splay(x), c[x][1]=i,pushup(x);}
    inline int treeroot(int x){access(x);splay(x);while(c[x][0])x=c[x][0];return x;}
    inline void makeroot(int x){access(x);splay(x);rev[x]^=1;}// 让x变成根
    inline void cut(int x,int y){makeroot(x);access(y);splay(y);f[x]=c[y][0]=0;pushup(y);}
    inline void link(int x,int y){makeroot(x);f[x]=y;}
    inline void cut2(int i){
        makeroot(X[i]);
        if(treeroot(Y[i])!=X[i]) return;
        cut(X[i],n+i),cut(Y[i],n+i),e.erase(i);
    }
    inline void link2(int i){
        makeroot(X[i]);
        if(treeroot(Y[i])==X[i]) {// access(y) splay(y)
            int p=t[Y[i]]-n;
            if(W[p]>=W[i]) return;// 这个非常重要
            cut(X[p],n+p),cut(Y[p],n+p),e.erase(p);
        }
        link(X[i],n+i),link(Y[i],n+i),e.insert(i);
    }
}g;

const int E=2e5+555;
struct edge{int u,v,w;}e[E];

int read(){int x;scanf("%d",&x);return x;}
int main(){
    g.n=read(),g.m=read();
    for(int i=1;i<=g.m;++i) e[i].u=read(),e[i].v=read(),e[i].w=read();
    sort(e+1,e+1+g.m,[](edge&a,edge&b){return a.w<b.w;});
    for(int i=1;i<=g.m;++i) g.X[i]=e[i].u,g.Y[i]=e[i].v,g.W[i]=e[i].w;
    g.ini();
    int ans=1e9;
    for(int i=1;i<=g.m;++i){
        if(e[i].u==e[i].v) continue;
        g.link2(i);
        if(g.e.size()==g.n-1) ans=min(ans,g.W[*g.e.rbegin()]-g.W[*g.e.begin()]);
    }
    cout<<ans<<endl;
}

k度限制最小生成树

在最小生成树的要求下，多一个条件: 有一个定点的度数不能超过k。
k度限制最小生成树与k-1度限制最小生成树最多有一条边的区别。
时间复杂度O(ElgE+kV) k度限制最小生成树
k度限制最小生成树代码
poj1639view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//poj1639-k度限制最小生成树
// #include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <cstdio>
using namespace std;
typedef pair<int, int> pii;
typedef map<int, int>::iterator IT;

const int V = 1e4, E = 1e5;
struct edge {
  int u, v, w;
  bool operator<(const edge& rhs) const { return w < rhs.w; }
} e[E], mxway[V];
map<int, int> g[V];
int lens[V];
int f[V];
int find(int u) { return u == f[u] ? u : f[u] = find(f[u]); }
void addedge(int u, int v, int w) {
  if (g[u].find(u) != g[u].end()) w = min(w, g[u][v]);
  g[u][v] = g[v][u] = w;
}
void eraedge(int u, int v) { g[u].erase(v), g[v].erase(u); }

void dfs(int u, int father) {
  // for (pii x : g[u]) {
  for (IT it = g[u].begin(); it != g[u].end(); ++it) {
    pii x = *it;
    if (x.first == father) continue;
    if (x.second > mxway[u].w)
      mxway[x.first] = edge{u, x.first, x.second};
    else
      mxway[x.first] = mxway[u];
    dfs(x.first, u);
  }
}

int klimitmst(int n, int m, int k) {
  int res = 0;
  // 求最小森林
  sort(e + 1, e + m + 1);
  for (int i = 1; i <= n; ++i) f[i] = i, lens[i] = 2e9;
  for (int i = 1; i <= m; ++i) {
    if (e[i].u > e[i].v) swap(e[i].u, e[i].v);
    if (e[i].u == 1 || find(e[i].u) == find(e[i].v)) continue;
    addedge(e[i].u, e[i].v, e[i].w);
    f[find(e[i].u)] = find(e[i].v);
    res += e[i].w;
  }
  // 求最小k0限制生成
  int k0 = 0;
  for (int i = 1; i <= m; ++i) {
    if (e[i].u == 1) {
      if (find(e[i].u) == find(e[i].v)) {
        lens[e[i].v] = min(lens[e[i].v], e[i].w);
      } else {
        addedge(e[i].u, e[i].v, e[i].w);
        f[find(e[i].u)] = find(e[i].v);
        res += e[i].w;
        k0++;
      }
    }
  }
  // 求最小k限制生成树
  for (k0++; k0 <= k; k0++) {
    for (int i = 1; i <= n; ++i) mxway[i].w = -1;
    for (IT it = g[1].begin(); it != g[1].end(); ++it) dfs(it->first, 1);
    // for (pii x : g[1]) dfs(x.first, 1);
    int p = 2;
    for (int i = 3; i <= n; ++i) {
      if (lens[i] != 2e9 && lens[i] - mxway[i].w < lens[p] - mxway[p].w) p = i;
    }
    // cout << lens[p] << " " << mxway[p].w << endl;
    if (lens[p] - mxway[p].w >= 0) break;
    eraedge(mxway[p].u, mxway[p].v);
    addedge(1, p, lens[p]);
    res += lens[p] - mxway[p].w;
    lens[p] = 2e9;
  }
  return res;
}

int read() {
  int x;
  scanf("%d", &x);
  return x;
}

int main() {
  // int n = read(), m = read(), k = read();
  // for (int i = 1; i <= m; ++i)
  //   e[i].u = read(), e[i].v = read(), e[i].w = read();
  // cout << klimitmst(n, m, k) << endl;
  int n = 0, m = read();
  map<string, int> id;
  id["Park"] = ++n;
  for (int i = 1; i <= m; ++i) {
    string s1, s2;
    cin >> s1 >> s2;
    if (id.find(s1) == id.end()) id[s1] = ++n;
    if (id.find(s2) == id.end()) id[s2] = ++n;
    e[i] = edge{id[s1], id[s2], read()};
  }
  cout <<"Total miles driven: "<< klimitmst(n, m, read()) << endl;
}

最小直径生成树

给无向连通图，求一个直径最小的生成树。 以图的绝对中心为根的最短路树，是一个最小直径生成树。先用floyd求多源最短路，然后对每一条边，假设绝对中心在此边上，求出该绝对中心的偏心率，可以考虑从大到小枚举最短路闭包来实现，汇总得到绝对中心，最终以绝对中心为根，求最短路树。 时间复杂度O(n3)
最小直径生成树代码
spoj1479view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//spoj1479-最小直径生成树
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= int(k); ++i)
using namespace std;
typedef pair<int, int> pii;
struct MDST {
  static const int V = 210;
  int d[V][V], g[V][V], vis[V], rk[V][V], tocen[V], n;
  void init(int _n) {  // O(n^2)
    n = _n;
    rep(i, 1, n) {
      rep(j, 1, n) g[i][j] = 1e9;
      g[i][i] = 0;
    }
  }
  void addedge(int u, int v, int w) {
    g[u][v] = g[v][u] = min(g[u][v], 2 * w);
  }                                                //将边权扩大一倍
  void centra(int& l, int& r, int& dl, int& dr) {  // 图的绝对中心 O(n^3)
    rep(i, 1, n) rep(j, 1, n) d[i][j] = g[i][j];
    rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) d[i][j] =
        min(d[i][j], d[i][k] + d[k][j]);

    rep(i, 1, n) {
      rep(j, 1, n) rk[i][j] = j;
      rep(j, 1, n) rep(k, j + 1, n) if (d[i][rk[i][j]] > d[i][rk[i][k]])
          swap(rk[i][j], rk[i][k]);
    }
    int ans = 1e9;
    rep(u, 1, n) {
      if (d[u][rk[u][n]] * 2 < ans) ans = d[u][rk[u][n]] * 2, l = r = u;
      rep(v, 1, n) if (g[u][v] != 1e9) {
        for (int ii = n, mx = 0; ii >= 1; ii--) {
          int i = rk[u][ii];
          if (abs(mx - d[u][i]) < g[u][v]) {//两边相差小于边权，才能假设绝对中心在这条边上
            int t = mx + d[u][i] + g[u][v];
            if (t < ans) {
              ans = t, l = u, r = v;
              dl = t / 2 - d[u][i];
              dr = g[u][v] - dl;
            }
          }
          mx = max(mx, d[v][i]);
        }
      }
    }
    cout << ans / 2 << endl;
  }
  void spt() {  // O(n^2)
    int l, r, dl, dr;
    centra(l, r, dl, dr);
    rep(i, 1, n) vis[i] = 0, tocen[i] = min(d[l][i] + dl, d[r][i] + dr);
    rep(i, 1, n) rep(j, 1, n) {  // j -> i
      if (i != l && i != r && i != j && tocen[j] + g[j][i] == tocen[i]) {
        cout << min(i, j) << " " << max(i, j) << endl;
        break;
      }
    }
    cout << min(l, r) << " " << max(l, r) << endl;
  }
} g;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  g.init(n);
  rep(i, 1, m) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    g.addedge(u, v, w);
  }
  g.spt();
}

最小比值生成树

有一个无向带权图(权为正数)，每条边有权xi和权yi，需要求出一个生成树T，记X=∑i∈Txi,Y=∑i∈Tyi,要求最小化比值XY. 我们设r=XY则有rY−X=0我们定义函数f(r)=rY−X，为当以ryi−xi作为权值的时候的最大生成树的值，这里显然f(r)关于r单调增，当我们找到一个r使得f(r)等于0的时候，r就是我们分数规划要的答案。 时间复杂度O(lgn)∗O(MST)
最小比值生成树代码
poj2728view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//poj2728-最小比值生成树
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <assert.h>
using namespace std;
// 完全图用prim算法复杂度为O(n^2)
const int V = 1e3 + 5;
double A[V][V], B[V][V], W[V][V];
double totree[V];

int mst[V];
int x[V], y[V], h[V];

int main() {
  int n;
  while (scanf("%d", &n), n) {
    for (int i = 1; i <= n; i++) scanf("%d%d%d", x + i, y + i, h + i);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        double dx = x[i] - x[j], dy = y[i] - y[j], dh = h[i] - h[j];
        A[i][j] = fabs(dh);
        B[i][j] = sqrt(dx * dx + dy * dy);
      }
    }
    double l = 0, r = 100;
    while (r - l > 1e-8) {// 二分
      double mid = (l + r) / 2;
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) W[i][j] = mid * B[i][j] - A[i][j];// 分数规划

      int s = 1;
      for (int i = 1; i <= n; i++) mst[i] = 0, totree[i] = W[s][i]; // 距离
      mst[s] = 1;
      double sum = 0;
      for (int t = 2; t <= n; t++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
          if (mst[i] == 0 && (u == -1 || totree[u] < totree[i])) u = i;
        mst[u]=1;
        sum+=totree[u];// 取出最远的点，求最大生成树
        for (int i = 1; i <= n; i++) 
          if(mst[i]==0) totree[i] = max(totree[i], W[u][i]);//只有不在生成树中的点才被松弛
      }// 生成树[?...sum] 与比值保持一致的单调性   

      sum > 0 ? r = mid : l = mid;// sum 大于0 则比值可以下降，则下移上界，反之上移下届
    }
    printf("%.3f\n", l);
  }
}