BZOJ1977: [BeiJing2010组队]次小生成树 Tree【Kruskal】

1977: [BeiJing2010组队]次小生成树 Tree

【题目描述】

传送门

【题解】

这题其实就是放大了数据范围,和普通的次小生成树一样,只不过需要用LCA找最大值,还得记录一个次大值,如果最大值等于这条边的

权值,就取次大值。

代码如下

#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN=1e5+5,MAXM=3e5+5;
int n,m,Dep[MAXN],fa[MAXN],Fa[MAXN][30],F[2][MAXN][30];
LL V,Ans=1e18;
struct xcw{
    int x,y,w;bool t;
    bool operator <(const xcw b)const{return w<b.w;}
}a[MAXM];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN<<1],son[MAXN<<1],W[MAXN<<1];
    void Add(int x,int y,int w){nxt[++tot]=lnk[x],son[tot]=y,W[tot]=w,lnk[x]=tot;}
}E;
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
void Cal(int i,int j,int fa){
    F[0][i][j]=F[0][i][j-1],F[1][i][j]=F[1][i][j-1];
    if(F[0][fa][j-1]>F[0][i][j]) F[1][i][j]=F[0][i][j],F[0][i][j]=F[0][fa][j-1];else
    if(F[0][fa][j-1]<F[0][i][j]&&F[0][fa][j-1]>F[1][i][j]) F[1][i][j]=F[0][fa][j-1];
    if(F[1][fa][j-1]<F[0][i][j]&&F[1][fa][j-1]>F[1][i][j]) F[1][i][j]=F[1][fa][j-1];
}
int Init(){
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i<=n;i++) Fa[i][j]=Fa[Fa[i][j-1]][j-1],Cal(i,j,Fa[i][j-1]);
}
int G(int x,int i,int w){
    if(F[0][x][i]==w) return F[1][x][i];
    else return F[0][x][i];
}
int LCA(int x,int y,int w){
    int MAX=0;
    if(Dep[x]<Dep[y]) swap(x,y);
    int Del=Dep[x]-Dep[y];
    for(int i=0;(1<<i)<=Del;i++) if((1<<i)&Del) MAX=max(G(x,i,w),MAX),x=Fa[x][i];
    if(x==y) return MAX;
    for(int i=log2(n);i>=0;i--)
    if(Fa[x][i]!=Fa[y][i]) MAX=max(max(G(x,i,w),G(y,i,w)),MAX),x=Fa[x][i],y=Fa[y][i];
    return max(max(G(x,0,w),G(y,0,w)),MAX);
}
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
void DFS(int x,int FA){
    Fa[x][0]=FA;Dep[x]=Dep[FA]+1;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(E.son[j]!=FA) F[0][E.son[j]][0]=E.W[j],DFS(E.son[j],x);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read(),m=read();
    for(int i=1;i<=m;i++) a[i]=(xcw){read(),read(),read()};
    sort(a+1,a+1+m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int fx=get(a[i].x),fy=get(a[i].y);
        if(fx==fy) continue;
        fa[fy]=fx,V+=a[i].w,a[i].t=1,E.Add(a[i].x,a[i].y,a[i].w),E.Add(a[i].y,a[i].x,a[i].w);
    }
    DFS(1,0);Init();
    for(int i=1;i<=m;i++)
    if(!a[i].t) Ans=min(Ans,V-LCA(a[i].x,a[i].y,a[i].w)+a[i].w);
    printf("%lld\n",Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部