生成树算法

补一篇生成树(Spanning Tree)的文章


生成树

一个比较鬼扯的定义:对于一个图 ,它的生成树是一个连通子图 ,其中

最小生成树

对于一个加权图 G,最小生成树(Minimum Spanning Tree,MST)指的是边权和最小的生成树。

最小生成树的算法主要有 Prim 和 Kruskal 算法

次小生成树

非严格的次小生成树是指图 G 的一棵生成树,使得这个生成树与 G 的 MST 形态不同,边权和最小,通俗的理解,就是 “除了 MST 之外的边权和最小的树”。由于有些图的 MST 不唯一,因此非严格的次小生成树有时候就是这个图的 MST 之一。

严格的次小生成树就是指边权和严格大于 MST 的边权和最小的生成树。

次小生成树的求解基于 MST。我们求解出 MST 后,将它建树型结构。对于那些剩下的不在 MST 中的边 (u,v),我们考虑把它添加到 MST 中,同时从 MST 中删除一条边。删除哪一条边呢?显然 MST 上从 u 到 v 的路径上任意一条边都可以。那么我们为了构造次小生成树,显然选择删除最大的边。因此问题转化为求树上 u 到 v 路径的最大边,这个可以用树上倍增维护。算法总复杂度为 .

[POJ1679] The Unique MST

问一个图的 MST 是否唯一

由于数据极小,暴力能过。更好的方法是求出次小生成树然后与 MST 比较。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e3,M=1e5,LOG_N=13;
int n,m;

struct qxx{int nex,t,v;};
qxx e[M];
int h[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;
}

struct data{// 双向边
    int u,v,w;
    void read(){scanf("%d%d%d",&u,&v,&w);}
};
bool cmp(data x,data y){return x.w<y.w;}
data d[M];

namespace DIS{// 并查集
    int f[N];
    void init(int k){for(int i=0;i<=k;i++)f[i]=i;}
    int gf(int u){return f[u]==u?u:f[u]=gf(f[u]);}
    void un(int u,int v){f[gf(u)]=gf(v);}
    bool find(int u,int v){return gf(u)==gf(v);}
}

int par[N],val[N],dep[N];// 倍增时用的指针,val 表示父边权值
int fp[N][LOG_N],fv[N][LOG_N];// 父结点,权值
void dfs(int u,int p){// 构造父结点指针,顺便做树上倍增
    // 对结点 u 做倍增
    fp[u][0]=par[u],fv[u][0]=val[u];
    for(int j=1;j<LOG_N;j++){//2^j
        if(!fp[u][j-1])break;
        fp[u][j]=fp[fp[u][j-1]][j-1];
        fv[u][j]=max(fv[u][j-1],fv[fp[u][j-1]][j-1]);
    }
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
        if(v==p)continue;
        val[v]=w,par[v]=u,dep[v]=dep[u]+1;
        dfs(v,u);
    }
}

int calc(int u,int v){// 计算两点路径上的边权最大值
    if(dep[u]<dep[v])swap(u,v);
    int res=0;
    for(int i=LOG_N-1;i>=0;i--){// 跳 2^i 步
        if(!fp[u][i])continue;
        if(dep[u]-(1<<i)<=dep[v])continue;
        res=max(res,fv[u][i]), u=fp[u][i];
    }
    if(fp[u][0]==v)return res;//v 是 u 的祖先
    u=fp[u][0];
    for(int i=LOG_N-1;i>=0;i--){// 跳 2^i 步
        if(fp[u][i]==fp[v][i])continue;
        res=max(res, max(fv[u][i],fv[v][i]));
        u=fp[u][i],v=fp[v][i];
    }
    return res;
}

void go(){
    cnt=0;
    memset(h,0,sizeof(h));

    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)d[i].read();
    sort(d+1,d+m+1,cmp);

    DIS::init(n);
    int ans=0,sec=0x3f3f3f3f;
    bool vis[M]={0};
    for(int i=1;i<=m;i++){if(DIS::find(d[i].u,d[i].v))continue;
        DIS::un(d[i].u,d[i].v);
        add_path(d[i].u,d[i].v,d[i].w);
        add_path(d[i].v,d[i].u,d[i].w);
        ans+=d[i].w, vis[i]=1;// 已使用
    }

    par[1]=val[1]=0,dep[1]=1;
    memset(fp,0,sizeof(fp));
    memset(fv,0,sizeof(fv));
    dfs(1,0);// 构造父结点指针,1 为根结点

    for(int i=1;i<=m;i++){if(vis[i])continue;
        const int &u=d[i].u,&v=d[i].v,&w=d[i].w;
        int k=calc(u,v);
        sec=min(sec,ans+w-k);
    }
    if(sec==ans)puts("Not Unique!");
    else printf("%d\n",ans);
}
int main(){
    int t;
    scanf("%d",&t);
    while(--t>=0)go();
    return 0;
}

最小极差生成树

[POJ3522] Slim Span

求最大最小边权差最小的生成树

二分答案, 判定即可,复杂度 .

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=105, M=5e3+5;
int n,m;

struct data{
    int u,v,w;
    void read(){scanf("%d%d%d",&u, &v, &w);}
};
data d[M];
bool cmp(data x,data y){return x.w<y.w;}

namespace DIS{int f[N];
    void init(int k){for(int i=0;i<=k;i++)f[i]=i;}
    int gf(int k){return f[k]==k?k:f[k]=gf(f[k]);}
    void un(int u,int v){f[gf(u)]=gf(v);}
    bool find(int u,int v){return gf(u)==gf(v);}
}
bool check(int k){
    int end=1;
    for(int i=1;i<=m;i++){while(d[end].w-d[i].w<=k&&end<=m)++end;
        DIS::init(n);
        int tot=n;
        for(int j=i;j<end;j++){const int &u=d[j].u, &v=d[j].v;
            if(DIS::find(u,v))continue;
            DIS::un(u,v), --tot;
        }
        if(tot==1)return 1;
        if(end>m)break;
    }
    return 0;
}
void go(){for(int i=1;i<=m;i++)d[i].read();
    sort(d+1,d+m+1,cmp);
    int l=0,r=10001;
    while(l<r){int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(l==10001)puts("-1");
    else printf("%d\n",l);
}
int main(){while(~scanf("%d%d",&n,&m)){if(n==0&&m==0)break;
        go();}
    return 0;
}

最优比率生成树

对于图的每条边,有两个权值 ,求一个生成树 使得

最小化。

这个问题可以二分比率,然后求一个 的 MST 来判定。

[POJ2728] Desert King

给定 N 个平面上的点的坐标和它们的权值,任意两点之间的边的价值是它们的距离,费用是两点权值之差的绝对值,求该图的一棵生成树,使得该树所有边的费用之和与价值之和的比值最小(只需求这个比值即可)

模板题。可以二分,可以迭代(迭代的出锅了,贴一个二分的)


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e3+5;
const double EPS=1e-6;
int n;

struct point{
    int x,y,z;
    void read(){scanf("%d%d%d",&x,&y,&z);}
};

double sqr(int x){return x*x;}
double dist(point a, point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
double cost(point a, point b){return fabs(a.z-b.z);}

point p[N];
double d[N][N],c[N][N];

bool vis[N];
double w[N][N];
bool check(double k){for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            w[i][j]=w[j][i]=c[i][j]-d[i][j]*k;
    double low[N];
    for(int i=0;i<=n;i++)low[i]=1e9,vis[i]=0;
    low[1]=0;
    for(int i=1;i<=n;i++){int u=0;//low[0]==INF
        for(int j=1;j<=n;j++)
            if(!vis[j]&&low[j]<low[u])u=j;
        vis[u]=1;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&w[j][u]<low[j])
                low[j]=w[j][u];
    }
    double res=0;
    for(int i=1;i<=n;i++)res+=low[i];
    return res<0;}
bool go(){scanf("%d",&n);
    if(n==0)return 0;
    for(int i=1;i<=n;i++)p[i].read();
    for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){d[i][j]=d[j][i]=dist(p[i],p[j]);
            c[i][j]=c[j][i]=cost(p[i],p[j]);
        }
    }
    double l=0,r=1e2;
    while(fabs(r-l)>EPS){double mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    printf("%.3f\n",l);
    return 1;
}
int main(){while(go());
    return 0;
}

一些莫名奇妙的东西

前置知识

排列

一个元素集合 ,对于集合 到自身上的一一对应

那么 称为 的一个排列,记做

对换排列

任取一个排列 ,将其中两个相邻的元素 对换一下,便造出一个新的排列 称为原来排列的对换排列.

定理 1

将任意一个排列 通过对换变成标准排列 所需的对换次数的奇偶性与对换方式无关。

这个可以用逆序对来证。

奇偶排列

一个排列称为偶(奇)排列,如果有一种方式,经过偶(奇)数次对换后,可以将排列变为标准排列。

综上,引入符号

其中 是对换次数。

行列式

一至三阶行列式

先看一下行列式的例子

一阶行列式是一个变量 的函数 ,也可以改写为

其中 只有一种情况,所以整个式子的值为 .

二阶行列式是四个变量 的函数

可以改写为

其中 的排列,当 时式子的值为

时式子的值为 ,则整个式子的值为 .

同理,三阶行列式是关于九个变量 的函数:

n 阶行列式

n 阶矩阵 的行列式是一实数,记作 ,定义为

由行列式的定义可知,利用定义直接计算行列式是很困难的,只有在阶数低时才可以直接用定义计算

性质 1

对于 n 阶矩阵

即行列式的行和列的地位是平等的。确切地说,每个关于行的性质,对列必然成立;反之亦然。

性质 2

行列式的任两行(或两列)互换,行列式变号。

推论 行列式的某两行(或两列)相同时,行列式的值为 0.

性质 3

用实数 乘以一行(或列)后,所得到的行列式等于原来的行列式乘以 .

推论 行列式有两行(或两列)成比例,则该行列式的值为零。特别的,当行列式有一行(或列)全为零时,行列式的值为零。

性质 4

参考文献

周冬 , 《生成树的计数及其应用》 , 2007 国家集训队论文集


  转载请注明: Sshwy's Blog 生成树算法

 上一篇
[ZJOI2006] 书架 [ZJOI2006] 书架
题意要求对一个元素互不相同的整数序列维护以下操作: 把某个数放到序列开头(左端) 把某个数放到序列结尾 把某个数和它左边的数交换 把某个数和它右边的数交换 询问某一个数字在序列的位置 询问在序列上某一位置的数是多少 $n,m\leq 8
2019.01.18
下一篇 
[HAOI2012] 高速公路 [HAOI2012] 高速公路
题意Y901 高速公路是一条由 段路以及 个收费站组成的东西向的链,收费站依次编号为 ,从收费站 行驶到 (或从 行驶到 ) 需要收取一定的费用,高速路刚建成时所有的
2019.01.17
  目录