问题描述:

给你一张有n个节点m条边的无向图,需要你求出这张图的严格次小生成树。

输入:

第一行包含两个整数N 和M,表示无向图的点数与边数。
接下来 M行,每行 3个数x y z 表示,点 x 和点y之间有一条边,边的权值为z。

输出:

仅一个数,表示严格次小生成树的边权和。

思路:

这道题和POJ1639度限制生成树一样,先计算出最小生成树,然后在最小生成树的基础上进行调整,得到要求的答案。

我们知道最小生成树与次小生成树最多只有一条边不同。所以我们可以在已经求出最小生成树的基础上,枚举每一条不在树上的边。假设它是次小生成树上的边,那么我们既要保持树的结构还要使树尽可能小,这时我们就要删去这条边两端树上路径的最长边,然后利用这个更新答案。

但这就出现了一个问题,有可能这条删去的边的边权和我们加的边的边权相等,这时新的树依然是最小生成树。所以我们需要记录下两端树上路径的次长边,如果出现上面情况我们就删去次长边,这样就是严格树次小生成树了。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 100005
#define MAXE 300005
#define LL long long
#define INF 1e18
using namespace std;

int n, m, cnt, max1, max2, head[MAXN], f1[MAXN], f2[MAXN][25], dis[MAXN][25][2], dep[MAXN];
LL sum, ans=INF;

struct Edge {int x, y, dis; bool tag;} edge[MAXE];
struct Tree {int next, to, dis;} tree[MAXN*2];

bool CMP (Edge x, Edge y) {return x.dis<y.dis;}

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

void addedge(int from, int to, int dis)
{
    tree[++cnt].next=head[from];
    tree[cnt].to=to;
    tree[cnt].dis=dis;
    head[from]=cnt;
}

void kruskal()
{
    for(int i=1; i<=n; i++) f1[i]=i;
    sort(edge+1, edge+m+1, CMP);
    for(int i=1; i<=m; i++)
    {
        int fx=find(edge[i].x), fy=find(edge[i].y);
        if(fx!=fy)
        {
            f1[fx]=fy; sum+=edge[i].dis;
            edge[i].tag=true;
            addedge(edge[i].x, edge[i].y, edge[i].dis);
            addedge(edge[i].y, edge[i].x, edge[i].dis);
        }
    }
}

void dfs(int x, int fa)
{
    f2[x][0]=fa;
    for(int i=head[x]; i; i=tree[i].next)
    {
        int to=tree[i].to;
        if(to==fa) continue;
        dis[to][0][0]=tree[i].dis;
        dep[to]=dep[x]+1;
        dfs(to, x);
    }
}

void init()
{
    for(int i=1; i<=20; i++)
    {
        for(int j=1; j<=n; j++)
        {
            f2[j][i]=f2[f2[j][i-1]][i-1];
            dis[j][i][0]=max(dis[j][i-1][0], dis[f2[j][i-1]][i-1][0]);
            dis[j][i][1]=max(dis[j][i-1][1], dis[f2[j][i-1]][i-1][1]);
            if(dis[f2[j][i-1]][i-1][0]==dis[j][i-1][0]) continue;
            dis[j][i][1]=max(dis[j][i][1], min(dis[f2[j][i-1]][i-1][0], dis[j][i-1][0]));
        }
    }
}

int Lca(int x, int y)
{
    if(dep[x]<dep[y]) swap(x, y);
    for(int i=20; i>=0; i--) if(dep[f2[x][i]]>=dep[y]) x=f2[x][i];
    if(x==y) return x;
    for(int i=20; i>=0; i--) if(f2[x][i]!=f2[y][i]) x=f2[x][i], y=f2[y][i];
    return f2[x][0];
}

int solve(int x, int y, int len)
{
    int maxn=0;
    for(int i=20; i>=0; i--)
    {
        if(dep[f2[x][i]]>=dep[y])
        {
            if(dis[x][i][0]==len) maxn=max(maxn, dis[x][i][1]);
            else maxn=max(maxn, dis[x][i][0]);
            x=f2[x][i];
        }
    }
    return maxn;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].dis);
    kruskal();
    dfs(1, 0);
    init();
    for(int i=1; i<=m; i++)
    {
        if(edge[i].tag) continue;
        int lca=Lca(edge[i].x, edge[i].y);
        max1=solve(edge[i].x, lca, edge[i].dis);
        max2=solve(edge[i].y, lca, edge[i].dis);
        ans=min(ans, sum-max(max1, max2)+edge[i].dis);
    }
    printf("%lld\n", ans);
}

发表评论

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