次小生成树模板

次小生成树模板

【例题】

传送门

【做法】

先用最小生成树做出这棵树,然后DFS建树,插入一条非树边,肯定在树上形成了环,所以在环上找一个最大的删去,加入这条边。最后从所有情中选一个最小的就是答案。(首先得知道这个次小指的是什么次小,是值次小还是值从小到大排序后排名第二的,也就是涉及到次小是否能等于最小的问题)

贴上代码(Kruskal)

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN=505,MAXM=10005;
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],W[MAXN<<1],son[MAXN<<1],nxt[MAXN<<1];
    void Add(int x,int y,int w){son[++tot]=y,W[tot]=w,nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
int n,m,fa[MAXN],Dep[MAXN],L[MAXN];
LL Ans=1e18,Lev;
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
void DFS(int x,int FA){
    fa[x]=FA,Dep[x]=Dep[FA]+1;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(E.son[j]!=FA) L[E.son[j]]=E.W[j],DFS(E.son[j],x);
}
int Work(int x,int y,int w){
    int Now=0;
    while(x!=y){
        if(Dep[x]<Dep[y]) swap(x,y);
        if(L[x]!=w) Now=max(L[x],Now);//防止出现次小等于最小的情况
        x=fa[x];
    }
    return Now;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
    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,Lev+=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);
    for(int i=1;i<=m;i++) if(!a[i].t) Ans=min(Ans,Lev-Work(a[i].x,a[i].y,a[i].w)+a[i].w);
    printf("%lld\n",Ans);
    return 0;
}

发表评论

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

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

返回顶部