刷题记（次小生成树 - I）

CONTENT: 次小生成树 - 1
PROBLEMS:
POJ 1679
CF 1108F

BB

Deemo能承包好几十篇的音乐！
其实次小生成树问题在前面学LCT的时候有道升级版“严格最小生成树”，这里也是因为后面那道CF的题目所以写的 QAQ

Introduction

次小生成树问题可以在最小生成树的基础上解决
下文皆考虑图是连通的，无重边的，无环的
在求完最小生成树的基础上，删掉MST上的任意一条边后，再求整幅图的MST，其中的最小值就是次小生成树
但是这样解复杂度不可接受
于是倒过来考虑，枚举不在MST上的边，尝试将其加入MST，此时必然成环，那么就应该删掉MST上且在环上的一条边，那么应该删掉哪一条边呢？应该删掉其中最大的边，因为损失的代价更少，即min(e_new - e_mst, ...)
于是问题的瓶颈就变成了 如何快速查询点对(u, v)路径上边的最大值

用DFS（或DP，可是蒟蒻不会 QAQ）求出MST上点对(u, v)上的最大距离d[u][v] O(n^2)
用lca倍增方法求出最大距离，查询时用求lca方法查询
用树链剖分 + 线段树的方法维护最大距离
用lct维护最大距离

The Unique MST - POJ - 1679

Link
https://vjudge.net/problem/POJ-1679
Description
求所给图中的MST是否唯一，若唯一则输出MST的值，否则输出Not Unique!
Sample Input

Sample Output

3
Not Unique!

Solution

#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 105;
const int M = N * N + 15;
const int BASE = 10;
const int inf = 0x3f3f3f3f;
typedef long long ll;

struct edge{
    int v, w, nxt;
};
struct InputEdge {
    int u, v, w;

    bool operator < (const InputEdge& b) const {
        return w < b.w;
    }
};

InputEdge in[M];
edge e[M];
int  head[N], tot;
int  fa[N][BASE + 1], dpt[N];
int val[N][BASE + 1];
int ft[N];
bool used[N];

inline int find(int x) {
    return ft[x] == x ? x : ft[x] = find(ft[x]);
}

void merge(int x, int y) {
    int p = find(x), q = find(y);
    if(p != q) {
        ft[q] = p;
    }
}

inline void init(){
    memset(head, -1, sizeof(head));
    memset(fa, -1, sizeof(fa));
    dpt[1] = 0;
    tot = 0;
}

inline void addEdge(int u, int v, int w){
    e[tot] = edge{v, w, head[u]};
    head[u] = tot++;
}

void dfs(int u, int pre){
    for(int i = head[u]; ~i; i = e[i].nxt){
        int v = e[i].v;
        if(v == pre)    continue;
        dpt[v] = dpt[u] + 1;
        fa[v][0] = u;
        val[v][0] = e[i].w;
        dfs(v, u);
    }
}

void getFa(int n){
    for(int j = 1; j <= BASE; j++){
        for(int i = 1; i <= n; i++){
            if(fa[i][j - 1] == -1)  continue;
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            val[i][j] = max(val[i][j - 1], val[fa[i][j - 1]][j - 1]);
        }
    }
}

int getMaxDis(int u, int v){
    int ret = 0;

    if(dpt[u] > dpt[v])     swap(u, v);
    for(int j = BASE; j >= 0; j--){
        if(fa[v][j] == -1 || dpt[fa[v][j]] < dpt[u]) {
            continue;
        }
        ret = max(ret, val[v][j]);
        v = fa[v][j];
    }
    if(u == v)  return ret;
    for(int j = BASE; j >= 0; j--){
        if(fa[u][j] == -1 || fa[v][j] == -1 || fa[u][j] == fa[v][j])    continue;
        ret = max(ret, max(val[u][j], val[v][j]));
        u = fa[u][j], v = fa[v][j];
    }

    ret = max(ret, max(val[u][0], val[v][0]));

    return ret;
}

int kruskal(int n, int m) {
    for(int i = 1; i <= n; i++) {
        ft[i] = i;
    }
    memset(used, false, sizeof(used));
    init();

    sort(in, in + m);

    int ret = 0;
    for(int i = 0; i < m; i++) {
        if(find(in[i].u) != find(in[i].v)) {
            ret += in[i].w;
            used[i] = true;
            merge(in[i].u, in[i].v);
            addEdge(in[i].u, in[i].v, in[i].w);
            addEdge(in[i].v, in[i].u, in[i].w);
        }
    }
    return ret;
}

int solve(int n, int m) {
    int ret = kruskal(n, m);
    dfs(1, -1);
    getFa(n);

    int sum = inf;
    for(int i = 0; i < m; i++) {
        if(used[i]) {
            continue;
        }
        sum = min(sum, in[i].w - getMaxDis(in[i].u, in[i].v));
    }

    return (sum == 0 ? -1 : ret);
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &in[i].u, &in[i].v, &in[i].w);
        }

        int ans = solve(n, m);
        if(ans == -1) {
            puts("Not Unique!");
        } else {
            printf("%d\n", ans);
        }
    }
}

MST Unification - CodeForces - 1108F

Link
https://cn.vjudge.net/problem/CodeForces-1108F
Description
给定一幅图，现在有一种操作可以将图中的任意一条边的值+1，操作可以进行无数次，且对任意一条边都可以使用无数次，现在问最小操作次数为多少时能使得图中的MST唯一
Sample Input

Sample Output

Solution
实际上就是使得次小生成树严格，那么求次小生成树时若该边等于环上最大边，就需要+1，统计一下+1次数！

#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2e5 + 15;
const int M = 2e5 + 15;
const int BASE = 17;
const int inf = 0x3f3f3f3f;
typedef long long ll;

struct edge{
    int v, w, nxt;
};
struct InputEdge {
    int u, v, w;

    bool operator < (const InputEdge& b) const {
        return w < b.w;
    }
};

InputEdge in[M];
edge e[M << 1];
int  head[N], tot;
int  fa[N][BASE + 1], dpt[N];
int val[N][BASE + 1];
int ft[N];
bool used[N];

inline int find(int x) {
    return ft[x] == x ? x : ft[x] = find(ft[x]);
}

void merge(int x, int y) {
    int p = find(x), q = find(y);
    if(p != q) {
        ft[q] = p;
    }
}

inline void init(){
    memset(head, -1, sizeof(head));
    memset(fa, -1, sizeof(fa));
    dpt[1] = 0;
    tot = 0;
}

inline void addEdge(int u, int v, int w){
    e[tot] = edge{v, w, head[u]};
    head[u] = tot++;
}

void dfs(int u, int pre){
    for(int i = head[u]; ~i; i = e[i].nxt){
        int v = e[i].v;
        if(v == pre)    continue;
        dpt[v] = dpt[u] + 1;
        fa[v][0] = u;
        val[v][0] = e[i].w;
        dfs(v, u);
    }
}

void getFa(int n){
    for(int j = 1; j <= BASE; j++){
        for(int i = 1; i <= n; i++){
            if(fa[i][j - 1] == -1)  continue;
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            val[i][j] = max(val[i][j - 1], val[fa[i][j - 1]][j - 1]);
        }
    }
}

int getMaxDis(int u, int v){
    int ret = 0;

    if(dpt[u] > dpt[v])     swap(u, v);
    for(int j = BASE; j >= 0; j--){
        if(fa[v][j] == -1 || dpt[fa[v][j]] < dpt[u]) {
            continue;
        }
        ret = max(ret, val[v][j]);
        v = fa[v][j];
    }
    if(u == v)  return ret;
    for(int j = BASE; j >= 0; j--){
        if(fa[u][j] == -1 || fa[v][j] == -1 || fa[u][j] == fa[v][j])    continue;
        ret = max(ret, max(val[u][j], val[v][j]));
        u = fa[u][j], v = fa[v][j];
    }

    ret = max(ret, max(val[u][0], val[v][0]));

    return ret;
}

void kruskal(int n, int m) {
    for(int i = 1; i <= n; i++) {
        ft[i] = i;
    }
    memset(used, false, sizeof(used));
    init();

    sort(in, in + m);

    for(int i = 0; i < m; i++) {
        if(find(in[i].u) != find(in[i].v)) {
            used[i] = true;
            merge(in[i].u, in[i].v);
            addEdge(in[i].u, in[i].v, in[i].w);
            addEdge(in[i].v, in[i].u, in[i].w);
        }
    }
}

int solve(int n, int m) {
    kruskal(n, m);
    dfs(1, -1);
    getFa(n);

    int ret = 0;
    for(int i = 0; i < m; i++) {
        if(used[i]) {
            continue;
        }
        if(in[i].w == getMaxDis(in[i].u, in[i].v)) {
            ret++;
        }
    }

    return ret;
}

int main(){
    int n, m;
    while(~scanf("%d%d", &n, &m)){
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &in[i].u, &in[i].v, &in[i].w);
        }

        printf("%d\n", solve(n, m));
    }
}