bzoj 1977 洛谷P4180 严格次小生成树

Description：

给定一张N个节点M条边的无向图，求该图的严格次小生成树。设最小生成树边权之和为sum，那么严格次小生成树就是边权之和大于sum的最小的一个

Input：

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

Output：

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

思路：先求出原图的最小生成树，然后继续从小到大枚举边（x，y），对于x，y用倍增求LCA的同时用一个ST表维护两点间的最大值，取最小的差值即可

书上好像用的是倍增LCA的同时用两个dp维护最大值和次大值，表示并看不怎么懂……

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + ;

#define ll long long

int head[N], now;

struct edges{

    int u, to, next, w;

}edge[N<<];

void add(int u, int v, int w){ edge[++now] = {u, v, head[u], w}; head[u] = now;}

struct input{

    int u, v, w;

}E[N];

int n, m, father[N], fa[N][];

ll mx[N][], d[N], tot;

bool vis[N];

int get(int x){

    if(x != father[x]) return father[x] = get(father[x]);

    return x;

}

bool cmp(input x, input y){ return x.w < y.w; }

void kruskal(){

    sort(E + , E + m + , cmp);

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

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

        int x = get(E[i].u), y = get(E[i].v);

        if(x != y) father[y] = x, tot += E[i].w, add(E[i].u, E[i].v, E[i].w), add(E[i].v, E[i].u, E[i].w), vis[i] = ;

    }

}

void dfs(int x,int pre, int deep){

    fa[x][] = pre; d[x] = deep;

    for(int i = head[x]; i; i = edge[i].next){

        int v = edge[i].to;

        if(v == pre) continue;

        mx[v][] = edge[i].w;

        dfs(v, x, deep + );

    }

}

void work(){

    for(int j = ; j <= ; j++)

      for(int i = ; i <= n; i++){

        fa[i][j] = fa[fa[i][j - ]][j - ];

        mx[i][j] = max(mx[i][j - ], mx[fa[i][j - ]][j - ]);

      }

}

ll getmax(int x,int y, int z){

    if(y == -) return ;

    if(mx[x][y] == z) return max(getmax(x, y - , z), getmax(fa[x][y - ], y - , z));

    return mx[x][y];

}

ll query(int x, int y, int z){

    ll maxn = ;

    if(d[x] < d[y]) swap(x, y);

    if(d[x] ^ d[y])

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

        if(d[fa[x][i]] >= d[y]) maxn = max(maxn, getmax(x, i, z)), x = fa[x][i];

    if(x == y) return z - maxn;

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

        if(fa[x][i] != fa[y][i]){

            maxn = max(maxn, max(getmax(x, i, z), getmax(y, i, z)));

            x = fa[x][i], y = fa[y][i];

        }

    }

    return z - max(maxn, max(getmax(x, , z), getmax(y, , z)));

}

int main(){

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

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

      scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);

    kruskal();

    dfs(, , );

    work();

    ll ans = 1e18;

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

      if(!vis[i]){

        ll tmp = query(E[i].u, E[i].v, E[i].w);

        if(tmp) ans = min(ans, tot + tmp);

      }

    printf("%lld\n", ans);

    return ;

}

巴特西

bzoj 1977 洛谷P4180 严格次小生成树

最新文章

热门文章