BZOJ 1016 - [JSOI2008]最小生成树计数

#图论 #生成树 #最小生成树

Published on 2016-08-22

描述

现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对 $31011$ 的模就可以了。

分析

根据 Kruskal 算法的过程，我们可以得到以下几个定理：

定理一：如果 $A, B$ 同为 $G$ 的最小生成树，且 $A$ 的边权从小到大为 $w(a_1), w(a_2), w(a_3), \cdots w(a_n)$ ， $B$ 的边权从小到大为 $w(b_1), w(b_2), w(b_3), \cdots w(b_n)$ ，则有 $w(a_i) = w(b_i)$ 。
证明：设 $A, B$ 第一个不同的边的下标为 $i$ ，不妨设 $w(a_i) \le w(b_i)$ ，如果不存在这样的 $i$ ，无需证明。
情况一： $a_i$ 在 $B$ 中，为 $b_j$ 。那么显然有 $j>i$ （否则 $i$ 不是第一个不同的边），则有 $w(a_i)\le w(b_i) \le w(b_j) = w(a_i)$ ，所以有 $w(a_i) = w(b_i) = w(b_j)$ ，所以可以调换 $b_i, b_j$ 的位置， $B$ 的权值排列不会改变， $A$ 与 $B$ 这样前 $i$ 条边均为相等，可以递归下去证明。
情况二： $a_i$ 不在 $B$ 中。考虑将 $a_i$ 加入 $B$ ，则形成了一个环，环中的权值 $v\le w(a_i)$ （否则 $B$ 不是最小生成树），且一定有一条边 $b_j$ 不在 $B$ 中，此时仍有 $j>i$ （否则 $i$ 不是第一个不同的边），所以有 $w(a_i)\le w(b_i) \le w(b_j) \le w(a_i)$ ，所以仍有 $w(a_i) = w(b_i) = w(b_j)$ ，可以将 $b_j$ 替换为 $a_i$ ， $B$ 的权值排列不会改变且仍为最小生成树，仍然调换 $b_i, b_j$ 的位置， $B$ 的权值排列仍会改变，这样 $A$ 与 $B$ 前 $i$ 条边均为相等，可以递归下去证明。这样换边不会有问题，因为 Kruskal 算法中唯一的状态就是连通性，我们没有改变其连通性，所以是可以递归证明的。

定理二：如果 $A, B$ 同为 $G$ 的最小生成树，如果 $A, B$ 都从零开始从小到大加边（ $A$ 加 $A$ 的边， $B$ 加 $B$ 的边）的话，每种权值加完后图的联通性相同。
证明：归纳法证明，没有边时显然成立，假设对于权值小于 $v$ 的成立。考虑权值为 $v$ 的边，如果连通性不相同，必然存在 $u, v$ 两点间连通性不同，假设 $A$ 中 $u, v$ 联通，根据 $A, B$ 所有小于 $v$ 的边连通性相同，所以必然存在一条 $u\rightarrow v$ 权值为 $v$ 的边，而根据 Kruskal 算法的执行过程， $B$ 不可能不加这条边，所以两棵最小生成树 $A, B$ 各自权值小于等于 $v$ 的边仍然满足连通性相同。由归纳法可知定理二成立。

定理三：如果在最小生成树 $A$ 中权值为 $v$ 的边有 $k$ 条，用任意 $k$ 条权值为 $v$ 的边替换 $A$ 中的权为 $v$ 的边且不产生环的方案都是一棵合法最小生成树。
证明：根据之前的定理，其余的边造成的连通性是定的，权值和也是定的，那么选 $k$ 条不产生环一定能形成一棵树，而且权值与最小生成树的权值一样，故也是最小生成树。

那么算法十分明确，随便找一个最小生成树（图不联通直接输出 0），记录下每种权值的出现次数，然后对于每种权值的边，分别求出方案（按照定理三的方法选），利用乘法原理即可解决。
复杂度： $O(2^{10}n^2\alpha(n))$ 。

代码

//  Created by Sengxian on 08/22/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1016 最小生成树 + 枚举 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100 + 3, maxm = 1000 + 3, modu = 31011;

struct edge {
    int from, to, cost;
    inline bool operator < (const edge &ano) const {
        return cost < ano.cost;
    }
}edges[maxm];

int n, m;

namespace union_find_set {
    int fa[maxn];
    inline int init(int n) {
        for (int i = 0; i < n; ++i) fa[i] = i;
    }
    inline int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    inline void unite(int x, int y) {
        x = find(x), y = find(y);
        fa[x] = y;
    }
    inline bool same(int x, int y) {
        return find(x) == find(y);
    }
}
using namespace union_find_set;

vector<int> cost, num;
bool Kruskal() {
    init(n);
    sort(edges, edges + m);
    int last = -1, cnt = 0;
    for (int i = 0; i < m; ++i) {
        const edge &e = edges[i];
        if (!same(edges[i].from, edges[i].to)) {
            cnt++;
            unite(edges[i].from, edges[i].to);
            if (edges[i].cost != last) {
                cost.push_back(edges[i].cost);
                num.push_back(1);
                last = edges[i].cost;
            } else num[num.size() - 1]++;
        }
    }
    return cnt == n - 1;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < m; ++i)
        edges[i].from = ReadInt() - 1, edges[i].to = ReadInt() - 1, edges[i].cost = ReadInt();
    if (!Kruskal()) return puts("0"), 0;
    int ans = 1, r = 0;
    init(n);
    for (int i = 0, j = 0; i < m; i = j) {
        int now_ans = 0;
        j = i + 1;
        while (j < m && edges[j].cost == edges[i].cost) ++j;
        if (edges[i].cost != cost[r]) continue;
        static int copy[maxn], ok[maxn];
        memcpy(copy, fa, sizeof (int) * n);
        for (int s = (1 << (j - i)) - 1; s; --s) if (__builtin_popcount(s) == num[r]) {
            memcpy(fa, copy, sizeof (int) * n);
            bool flag = true;
            for (int k = i; k < j; ++k) if ((s >> (k - i)) & 1) {
                if (same(edges[k].from, edges[k].to)) {flag = false; break;}
                unite(edges[k].from, edges[k].to);
            }
            if (flag) {
                now_ans++;
                if (now_ans == 1) memcpy(ok, fa, sizeof (int) * n);
            }
        }
        memcpy(fa, ok, sizeof (int) * n);
        (ans *= now_ans) %= modu;
        r++;
    }
    printf("%d\n", ans);
    return 0;
}

BZOJ 1018 - [SHOI2008]堵塞的交通traffic 莫比乌斯反演简要笔记

Sengxian's Blog

BZOJ 1016 - [JSOI2008]最小生成树计数

描述

分析

代码