HDU 5624 KK's Reconstruction 最小生成树

题意：这是bc round 71 div 1 的 1004 直接去看中文题意

分析：

首先，一种合法方案对应了原图的一棵生成树。

我们知道，最小生成树有一个性质是最大边最小。

因此，我们可以枚举生成树的最小边，去掉比该边小的边后对新图求最小生成树，那么我们所要的最优解一定包含在其中。

时间复杂度O(Mlog M+M^2*a (N)，显然仅仅这个效率是不够的。

可以发现我们每次枚举后都重新求了最小生成树，事实上这是不必要的。

考虑从大到小枚举生成树的最小边，我们要做的实际上是每次加入一条边，维护当前图的最小生成树。

加入一条边时，我们需要判断这条边能否与之前的边构成环。

I 若能构成环，用该边替代环中最大边一定更优；

II 若不能构成环，直接加入该边即可。

找环中最大边可以用DFS 实现。若图中现有的边数为N-1N−1，我们就可以更新答案。

这样，事件复杂度就降到了O(M\log M+MN)O(MlogM+MN)。

更高的效率的方法，我们涉及的操作为加边、删边、查询路径最大边，因此可以使用LCT 来维护。

注：我按照题解写了一发，肯定是我手残，没有理解人家的意思，我发现我写出来还没题解上的效率不行的快

肯定我不行，

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;

typedef long long LL;

const int maxn=;

const int mod=1e9+;

const LL INF=INT_MAX;

int head[maxn],p;

struct Edge

{

    LL u,v,next;

    LL w,mark;

    bool operator<(const Edge &e)const

    {

        return w<e.w;

    }

} edge[],o[];

void add(int u,int v,int w)

{

    edge[p].u=u;

    edge[p].v=v;

    edge[p].w=w;

    edge[p].mark=;

    edge[p].next=head[u];

    head[u]=p++;

}

int fa[maxn];

int find(int x)

{

    if(x==fa[x])return x;

    return fa[x]=find(fa[x]);

}

LL tmp,vv,_max;

void dfs(int u,int f,int res)

{

    if(u==vv)

        tmp=res;

    for(int i=head[u]; ~i; i=edge[i].next)

    {

        if(edge[i].v==f)continue;

        if(edge[i].mark)continue;

        _max=max(_max,edge[i].w);

        int c=res;

        if(res==-||edge[i].w>edge[c].w)c=i;

        dfs(edge[i].v,u,c);

    }

}

int main()

{

    int T,n,m;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=; i<=m; ++i)

            scanf("%I64d%I64d%I64d",&o[i].u,&o[i].v,&o[i].w);

        sort(o+,o++m);

        for(int i=; i<=n; ++i)fa[i]=i;

        p=;

        memset(head,-,sizeof(head));

        int cnt=;

        LL ans=INF;

        for(int i=m; i>; --i)

        {

            tmp=-,_max=,vv=o[i].v;

            if(cnt==n-)

            {

                dfs(o[i].u,,-);

                ans=min(ans,_max-o[i+].w);

            }

            int fx=find(o[i].u);

            int fy=find(o[i].v);

            if(fx!=fy)

            {

                ++cnt;

                fa[fx]=fy;

            }

            else

            {

                if(tmp==-)

                    dfs(o[i].u,,-);

                edge[tmp].mark=edge[tmp^].mark=;

            }

            add(o[i].u,o[i].v,o[i].w);

            add(o[i].v,o[i].u,o[i].w);

        }

        if(cnt==n-)

        {

            _max=;

            dfs(,,-);

            ans=min(ans,_max-o[].w);

        }

        if(ans==INF)printf("-1\n");

        else  printf("%I64d\n",ans);

    }

    return ;

}

巴特西

HDU 5624 KK's Reconstruction 最小生成树

最新文章

热门文章