题目大意:

给定一个无向图,求出该图的次小生成树,点数 $n≤100 000$ 边数 $m≤300 000$。

首先,思考暴力做法,求出最小生成树,从图中向树中加入一条边,显然, 图中就会出现一个环,而我们只需去掉环上次大的那条边(因为,最大的那条边肯定是刚加进去的,否则就不满足最小生成树的定义)。
时间复杂度:$O(mn)$。

code:

#include <bits/stdc++.h>
#define re register
using namespace std;
int read(){
    int f=1,r=0;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return r*f;
}
long long lread(){
    long long f=1,r=0;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return r*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void writein(int x){write(x);putchar('\n');}
const int MAXM=300001,MAXN=100001;

int f[MAXN];

int find(int x){
    if(x!=f[x])f[x]=find(f[x]);
    return f[x];
}

void unin(int x,int y){
    x=find(x),y=find(y);
    f[x]=y;
}

struct Edge{
    int from,to;
    long long dat;
}e[MAXM],e2[MAXM];

bool cmp(const Edge &q,const Edge &p){
    return q.dat<p.dat;
}

int n,m;
int num[MAXM],res;
long long minn,ans,sum;
bool flag;

void fa(){
    for(re int i=1;i<=n;i++)
        f[i]=i;
}

void kru1(){
    fa();
    sort(e+1,e+m+1,cmp);

    int cnt=0;
    for(re int i=1;i<=m;i++){
        int x=e[i].from,y=e[i].to;
        if(find(x)!=find(y)){
            unin(x,y);
            minn+=e[i].dat;
            cnt++;num[++res]=i;
            if(cnt==n-1)
                break;
        }
    }

}

void kru2(){
    for(re int i=1;i<=res;i++){
        int k=num[i];
        fa();
        sum=0;
        int tot=0;
        for(re int j=1;j<=m;j++){
            if(j==k) continue;
            int x=e[j].from,y=e[j].to;
            if(find(x)!=find(y)){
                unin(x,y);
                sum+=e[j].dat;
                tot++;
                if(tot==n-1)
                    break;
            }
        }
        if(!flag){
            if(sum>minn)
                ans=sum,flag=1;
        }
        else if(sum<ans && sum>minn)
            ans=sum;
    }
}

int main(){
    //freopen("tree.in","r",stdin);
    //freopen("tree.out","w",stdout);
    n=read(),m=read();
    for(re int i=1;i<=m;i++)
        e[i].from=read(),e[i].to=read(),e[i].dat=lread();
    kru1();
    kru2();
    writein(ans);
    return 0;
}

60 分到手。注:某 facker zqy 的代码。


wyz:轻松 AC 的题,为什么要部分分。

我们来思考如何优化。
很显然最小生成树不能优化,每一条非树边都必须被枚举,所以我们只能在求最大值上下手了。
这时候,我们考虑树上倍增法+LCA。
但是,LCA 如何记录路径上的最大值呢?
我们使用 $w$数组记录倍增的过程,$w[i][j]$记录 $j$向上 $2^i$步中这一段路径中的最大值,而可以用 $f[i][j]$记录 $j$向上 $2^i$步到达的坐标,所以 DP 方程就呼之欲出了 $w[u][i+1]=max(w[u][i],w[f[u][i]][i])$。按照这个方案,我们就可以在 $O(n$$logn)$的时间内求出树上两点路径中边权最大值了,而这个方案将原来的一个 $n$变成了 $logn$, 就离成功又进了一步。
但是,我们的想法有一点瑕疵,在题目中要求的是严格次小,是 $<$而不是 $<=$,那怎么办呢?

wyz:你是个菜逼,这都不会


在 wyz 大佬的指导下,我们明白了,可以记录一个次大值,就可以维护了。
那么,不难得到,DP 方程就成功成为了:
当 $w[u][i]>w[f[u][i]][i]$  $w2[u][i+1]=max(w[f[u][i]][i],w2[f[u][i]][i])$
当 $w[u][i]<w[f[u][i]][i]$  $w2[u][i+1]=max(w[u][i],w2[f[u][i]][i])$
当 $w[u][i]=w[f[u][i]][i]]$ 直接继承上一段的就行了。
code:

#include<cstdio>
#include<algorithm>
using namespace std;

#define maxn 300003
#define INF 1000000000000000

inline int read(){
    int r=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+(c^48),c=getchar();
    return r*f;
}

struct E{
    int u,v,w;
    E() {}
    E(int u,int v,int w):u(u),v(v),w(w) {};
    bool operator <(const E &edge) const{
        return w<edge.w;
    }
}e[maxn];

struct G{
    struct E{
        int v,w,nxt;
        E() {}
        E(int v,int w,int nxt):v(v),w(w),nxt(nxt) {};
    }e[maxn*2];

    int s_e,head[maxn];

    inline void a_e(int u,int v,int w){
        e[++s_e]=E(v,w,head[u]);
        head[u]=s_e;
    }
}t,g;

int n,m,er[25],lg[maxn],f[maxn],dep[maxn],anc[25][maxn];

long long sum,ans=INF,dp[25][maxn][2];

int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    anc[0][u]=fa;
    for(int i=t.head[u];i;i=t.e[i].nxt){
        int v=t.e[i].v,w=t.e[i].w;
        if(v==fa)continue;
        dp[0][v][0]=w;
        dp[0][v][1]=-INF;
        dfs(v,u);
    }
}

inline void init(){
    dfs(1,1);
    er[0]=1,lg[0]=-1;
    for(int i=1;i<=n;i++)lg[i]=lg[(i>>1)]+1;
    for(int i=1;i<=lg[n];i++)er[i]=er[i-1]<<1;
    for(int i=1;i<=lg[n];i++)
        for(int j=1;j<=n;j++){
            anc[i][j]=anc[i-1][anc[i-1][j]];
            dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][anc[i-1][j]][0]);
            dp[i][j][1]=min(dp[i-1][j][0],dp[i-1][anc[i-1][j]][0]);
            if(dp[i][j][0]==dp[i][j][1])dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][anc[i-1][j]][1]);
        }
}

long long lca(int u,int v,long long dis){
    if(dep[u]>dep[v])swap(u,v);
    int c=dep[v]-dep[u];
    long long Max=-INF,c_Max=-INF;
    while(c){
        if(Max<dp[lg[c]][v][0])c_Max=max(Max,dp[lg[c]][v][1]),Max=dp[lg[c]][v][0];
        else if(dp[lg[c]][v][0]!=Max)c_Max=max(c_Max,dp[lg[c]][v][0]);
        else c_Max=max(c_Max,dp[lg[c]][v][1]);
        v=anc[lg[c]][v];
        c-=er[lg[c]];
    }
    if(u==v)return dis==Max?c_Max:Max;
    for(int i=lg[dep[u]];i>=0;i--){
        if(anc[i][u]==anc[i][v])continue;
        if(Max<max(dp[i][u][0],dp[i][v][0])){
            if(max(dp[i][u][0],dp[i][v][0])==min(dp[i][u][0],dp[i][v][0]))c_Max=max(Max,max(dp[i][u][1],dp[i][v][1]));
            else c_Max=max(Max,min(dp[i][u][0],dp[i][v][0]));
            Max=max(dp[i][u][0],dp[i][v][0]);
        }
        else if(max(dp[i][u][0],dp[i][v][0])!=Max)c_Max=max(c_Max,max(dp[i][u][0],dp[i][v][0]));
        else if(min(dp[i][u][0],dp[i][v][0])!=Max)c_Max=min(c_Max,max(dp[i][u][0],dp[i][v][0]));
        else c_Max=max(c_Max,max(dp[i][u][1],dp[i][v][1]));
        u=anc[i][u],v=anc[i][v];
    }
    if(Max<max(dp[0][u][0],dp[0][v][0])){
        if(max(dp[0][u][0],dp[0][v][0])==min(dp[0][u][0],dp[0][v][0]))c_Max=max(Max,max(dp[0][u][1],dp[0][v][1]));
        else c_Max=max(Max,min(dp[0][u][0],dp[0][v][0]));
        Max=max(dp[0][u][0],dp[0][v][0]);
    }
    else if(max(dp[0][u][0],dp[0][v][0])!=Max)c_Max=max(c_Max,max(dp[0][u][0],dp[0][v][0]));
    else if(min(dp[0][u][0],dp[0][v][0])!=Max)c_Max=min(c_Max,max(dp[0][u][0],dp[0][v][0]));
    else c_Max=max(c_Max,max(dp[0][u][1],dp[0][v][1]));
    return dis==Max?c_Max:Max;
}

int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        e[i]=E(u,v,w);
    }
    sort(e+1,e+1+m);
    for(int i=1,j=0;i<=m;i++){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        int fu=find(u),fv=find(v);
        if(fu==fv){
            g.a_e(u,v,w);
            continue;
        }
        f[fu]=fv;
        sum+=w;
        j++;
        t.a_e(u,v,w);
        t.a_e(v,u,w);
    }
    init();
    for(int u=1;u<=n;u++)
        for(int i=g.head[u];i;i=g.e[i].nxt){
            int v=g.e[i].v,w=g.e[i].w;
            ans=min(ans,sum-lca(u,v,w)+w);
        }
    printf("%lld",ans);
    return 0;
}

注:AK 巨佬 wyz 的代码
最后%%%%%%wyz%%%%%%%

分类: 文章

2 条评论

windrunner · 2019年10月2日 7:35 上午

谢谢

Remmina · 2019年9月30日 11:22 下午

QwQ
感谢投稿 OvO
对部分 latex 和代码块的格式稍微修改了一下
_(:з」∠)_

发表评论

电子邮件地址不会被公开。 必填项已用*标注