题解：P4809 [CCC 2018] 最大战略储备

· · 题解

题意

给你 n \times m 个点的类似网格图和 p 条横向航线，q 条纵向航线。横向航线 (u, v, w) 表示对于任意的 1 \le i \le n，第 i 行的 u 号点和第 i 行的 v 号点之间存在一条长为 w 的边。纵向航线同理。求最多删权值和为多少的边是的剩下的边仍联通。

题解

很容易想到题目要求的是所有边的权值和减去这个图的最小生成树的权值和。

考虑如何求最小生成树。

朴素的来看可以使用 kruskal 求解，时间复杂度 \mathcal{O}((np + mq) \log (np + mq) \alpha(np + mq))。

然后我们发现，对于一条航线得出的所有边，他们排序后一定在一起，因此，我们直接对于 p + q 条航线排序，每条航线，对其得出的所有边放在一起进行操作，时间复杂度 \mathcal{O}((p + q) \log (p + q) + (np + mq) \alpha(np + mq))。

接着我们发现对于一条横向航线 (u, v, w)，如果是在最开始没有加入任何边的时候，这条航线会造成 n \times w 的贡献，并使任意一行的第 u 列和第 v 列连通，我们称其为整个第 u 列和整个第 v 列连通。

我们再来看下图。

黑色的正方形表示一个点，红色表示会新造成贡献的边，绿色表示不会造成贡献的边

对于一个行 i, j, k 来看，行 i, j, k 是联通的，所以原本应造成的贡献的 3 条边只会有 1 条造成贡献，对于行 s, t 来看，他们独自为一个连通块，会各自造成一条边的贡献。

因此对于横向航线，n 行分成了多少连通块，这条横向航线就会造成多少条边的贡献。

纵向航线同理。

因此我们对于 p + q 条航线排序，每次看对应的方向分几个连通块，乘上这条边的权值即可。

时间复杂度 \mathcal{O}((p + q) \log (p + q) + (p + q) \alpha(p + q))。

代码

::::info[码风丑陋但可读性较高的代码]{open}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, p, q, sum, cnty, cntx, fa_x[100005], fa_y[100005];
struct node{
    int u, v, w, id;//u, v, w表示一条航线，id表示为横向还是纵向，id = 1为横向，id = 2为纵向
    bool operator < (const node t) const{
        return w < t.w;
    }
}x[200005];
//并查集
void init(){
    for(int i = 1; i <= m; i++){
        fa_x[i] = i;
    }
    for(int i = 1; i <= n; i++){
        fa_y[i] = i;
    }
}
int find_x(int x){
    return (fa_x[x] == x ? x : fa_x[x] = find_x(fa_x[x]));
}
int find_y(int x){
    return (fa_y[x] == x ? x : fa_y[x] = find_y(fa_y[x]));
}
void merge_x(int x, int y){
    int u = find_x(x), v = find_x(y);
    if(u != v){
        cnty--;//合并横向航线造成纵向的连通块减一
        fa_x[u] = v;
    }
}
void merge_y(int x, int y){
    int u = find_y(x), v = find_y(y);
    if(u != v){
        cntx--;//同上
        fa_y[u] = v;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> p >> q;
    for(int i = 1; i <= p; i++){
        cin >> x[i].u >> x[i].v >> x[i].w;
        x[i].id = 1, sum += n * x[i].w;//先加上所有边的权值
    }
    for(int i = p + 1; i <= p + q; i++){
        cin >> x[i].u >> x[i].v >> x[i].w;
        x[i].id = 2, sum += m * x[i].w;
    }
    sort(x + 1, x + p + q + 1);//吧p + q条航线排序
    init();//并查集初始化
    cntx = n, cnty = m;//初始横向为n个连通块，纵向为m个连通块
    for(int i = 1; i <= p + q; i++){
        if(x[i].id == 1){//横向航线
            if(find_x(x[i].u) == find_x(x[i].v)){//已经联通
                continue;
            }
            sum -= x[i].w * cntx;//减去造成的贡献
            merge_x(x[i].u, x[i].v);
        }
        else{//同上
            if(find_y(x[i].u) == find_y(x[i].v)){//
                continue;
            }
            sum -= x[i].w * cnty;
            merge_y(x[i].u, x[i].v);
        }
    }
    cout << sum;//输出答案
    return 0;
}

::::