CF343E Tutorial

· · 题解

首先，看到要求多个最小割，以及较小的数据范围，不难想到最小割树。

那么我们先把最小割树求出来吧。接下来我们来考虑怎么构造使得值最大。具体的，我们现在要构造一个排列 p_1, p_2, \dots, p_n 使得 \sum\limits_{i = 2}^n f(p_i, p_{i - 1}) 最大，其中 f 定义为两点间最小值。

发现这个值的上界是 \sum\limits_{i = 1}^n w_i，其中 w_i 为每条边的权值。而且手推一下发现这个是可以很好构造出来，以下提供一种并查集 + 链表的神秘构造方法。

首先，我们从大到小考虑每一条边。显然的，如果我们想要加入这条边的贡献，我们可以经过比这条边权值大的边，但是不能经过比这条边权值小的边。

发现对于边 (x,y)，假设其两端的边权比其大的边所构成的连通块的集合分别是 S, T，显然的，f(u,v) = f(x,y), u \in S, y \in T。

此时，我们可以做并查集：每次做完一条边之后，我们就把这两个点合并，每次通过并查集和链表找到 S 和 T 这两个集合对应的连通块，然后把他们在序列上拼接到一起使它们相邻，根据上面发现的性质，这样就使得这条边的贡献为 f(u,v)，即边权了，重复若干次这个过程，便可以构造出一种方案。

不妨给每一个点多开两个变量，一个作为链表的 next 指针，另一个，则指向这个链表的尾部（只用对并查集中的根节点维护这个），此时合并两个连通块的操作就变成了合并两个链表，由于上述两个指针的存在，合并可以做到 O(1)。具体的，我们可以这样合并：

假设下图是我们两个要合并的集合 S,T。

此时，我们便可以很好的理解指向链表尾部是什么意思了。首先，我们通过并查集找到了 S[1], T[1]。

通过图示的红色的边找到 S[4]，并从 S[4] 出发向 T[1] 连蓝色的边。

此时两个链表就已经拼在一起了。我们还要对 S[1] 维护指向链表尾部的指针。

通过红色边找到 T[3]，S[1] 改连 T[3]。

这样就完成了合并操作。

所以这部分的时间复杂度是 O(n) 的，总的时间复杂度是 O(n^3m)，经典网络流跑不满随便过。

最小割树由于怕代码长度限制就不放上来了，这里放主函数和合并部分。

int fath[N];
struct link {
    int nxt, ed;
}p[N];

int getf(int x) {
    return x == fath[x] ? x : (fath[x] = getf(fath[x]));
}

void merge(int x, int y) {
    x = getf(x), y = getf(y);
    if(x == y) return;
    // x -> y
    p[p[x].ed].nxt = y;
    p[x].ed = p[y].ed; // 这里即为上面一大堆描述的过程
    fath[y] = x;
    return;
}

int main() {
    scanf("%d%d", &n, &m);
    // namespace GHT 即为 Gomory-Hu Tree，最小割树，此处是预处理，下面的 build(int,int) 是构建
    for(int i = 1; i <= n; i++)
        GHT::s[i] = i;
    for(int i = 1; i <= m; i++)
        scanf("%d%d%d", &fr[i], &to[i], &val[i]);
    GHT::build(1, n);
    int tot = 0;
    // struct GHT_graph{}TG 即为最小割树所在的图
    for(int i = 1; i <= TG.e_sz; i++)
        tot += TG.e[i].w;
    printf("%d\n", tot);
    stable_sort(TG.e + 1, TG.e + TG.e_sz + 1);
    // 已经定义：friend bool operator < (edge x, edge y) {return x.w > y.w}
    for(int i = 1; i <= n; i++)
        fath[i] = i, p[i].nxt = i, p[i].ed = i;
    for(int i = 1; i <= TG.e_sz; i++)
        merge(TG.e[i].u, TG.e[i].v);
    int pr = getf(1);
    printf("%d", pr);
    while(p[pr].nxt != pr) {
        pr = p[pr].nxt;
        printf(" %d", pr);
    }
    printf("\n");
    return 0;
}