大视野 1016: [JSOI2008]最小生成树计数（最小生成树）

浏览数：14 / 时间：2015年06月09日

总结：此类题需要耐心观察规律，大胆猜想，然后证明猜想，得到有用的性质，然后解答。简单的说：找隐含性质。

传送门：http://61.187.179.132/JudgeOnline/problem.php?id=1016

题意：n个点m条边的图，问其最小生成树的个数（只要有一条边不同，就算不同）。n<100, m<1000 权值c < 10^9, 其中权相同的边的数量不会超过10条。

思路：

经过观察思考，得到以下结论：

任意两个最小生成树，将其所有边的边长排序后，将得到完全相同的结果。

意思是：只能用相同长度的边来代替，借此得到不同的最小生成树。

又因为每种权相同的边数不超过10,则可以用以下方法：

首先，生成一个最小生成树，得到其包含的所有权值以及数量。

其次，将其中某种权值的边删除，然后在图中取出所有权值相同的边，状态压缩暴力匹配。得到这种边可以组合的方案数。

将所有权值的边的方案数相乘，就得到答案。

时间复杂度：MlogM + n(2^10*n) + M

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define mod 31011
#define N 200

struct Edge{
    int a, b, c;
    bool operator < (const Edge &b) const {
        return c < b.c;
    }
}e[2000], mintre[200];

struct BCJ{
    int fa[N];
    void init(int n) {
        for (int i = 0; i <= n; i++) {
            fa[i] = i;
        }
    }
    int find(int u) {
        return fa[u]== u ? fa[u] : fa[u] = find(fa[u]);
    }
    void unin(int u, int v) {
        fa[find(v)] = find(u);
    }
}b;

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
        }
        sort(e, e+m);
        int top = 0;
        b.init(n);
        for (int i = 0; i < m; i++) {
            if (b.find(e[i].a) != b.find(e[i].b)) {
                b.unin(e[i].a, e[i].b);
                mintre[top++] = e[i];
            }
        }
        if (top != n-1) {
            puts("0");
            continue;
        }

        int minp = 0;
        int ep = 0;
        int ans = 1;
        while (true) {
            if (minp == top || ep == m) break;
            int nowc = mintre[minp].c;
            //printf("nowc = %d\n", nowc);
            BCJ nowTong;
            nowTong.init(n);
            for (int i = 0; i < top; i++) {
                if (mintre[i].c != nowc) {
                    nowTong.unin(mintre[i].a, mintre[i].b);
                }
            }

            int edgeNum = 0;
            while (ep < m && e[ep].c < nowc) ep++;
            while (ep < m && e[ep].c == nowc) {
                edgeNum++;
                ep++;
            }

            int nownum = 0;
            while (minp < top && mintre[minp].c == nowc) {
                nownum++;
                minp++;
            }
            if (edgeNum == nownum) continue;
            int end = (1<<edgeNum);
            int nowans = 0;
            BCJ tmpTong;
            for (int i = 0; i < end; i++) {
                int tmpi = i;
                int num = 0;
                while (tmpi) {
                    num += (tmpi&1);
                    tmpi>>=1;
                }
                if (num != nownum) continue;

                tmpTong = nowTong;
                tmpi = i;
                int unintime = 0;
                for (int j = ep-1; e[j].c == nowc; j--) {
                    if (tmpi&1) {
                        if (tmpTong.find(e[j].a) != tmpTong.find(e[j].b)) {
                            unintime++;
                            tmpTong.unin(e[j].a, e[j].b);
                        }
                    }
                    tmpi>>=1;
                }
                if (unintime == nownum) {
                    nowans++;
                }
            }
            ans *= nowans;
            ans %= mod;
        }
        printf("%d\n", ans);
    }
    return 0;
}