bzoj 第一题,矩阵树算法写起来炒鸡烦,就先去写了一发暴力的……
说是写的,其实基本是看着黄学长的代码敲的……

题意:
最小生成树计数。

思路:
请查阅本人关于最小生成树计数的粗浅证明文章。

注: 这道题你不手写读入会蜜汁WA

#include <bits/stdc++.h>

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

using namespace std;
const int mod = 31011;
const int maxn = 1005;

struct edge {
    int u, v, w;
    bool operator<(const edge& a) const
    {
        return w < a.w;
    }
} edges[maxn];

struct segment {
    int l, r, num;
} segs[maxn];

int n, m, cnt, tot, sum, ans = 1;
int root[maxn];

inline bool scan_d(int& num)
{
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF)
        return false;
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else
        num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
    if (IsN)
        num = -num;
    return true;
}

int findRoot(int x)
{
    return root[x] == x ? x : findRoot(root[x]);
}

void dfs(int id, int cur, int num)
{
    if (cur == segs[id].r + 1) {
        if (num == segs[id].num)
            sum++;
        return;
    }
    int ru = findRoot(edges[cur].u), rv = findRoot(edges[cur].v);
    if (ru != rv) {
        root[rv] = ru;
        dfs(id, cur + 1, num + 1);
        root[rv] = rv, root[ru] = ru;
    }
    dfs(id, cur + 1, num);
}

int main()
{
    scan_d(n),scan_d(m);
    range(i, 1, m)
        scan_d(edges[i].u),scan_d(edges[i].v),scan_d(edges[i].w);
    each(i, n + 1)
        root[i] = i;
    sort(edges + 1, edges + m + 1);
    range(i, 1, m)
    {
        if (edges[i].w != edges[i - 1].w) {
            segs[cnt].r = i - 1;
            segs[++cnt].l = i;
        }
        int ru = findRoot(edges[i].u), rv = findRoot(edges[i].v);
        if (ru != rv) {
            root[rv] = ru;
            segs[cnt].num++;
            tot++;
        }
    }
    segs[cnt].r = m ;
    if (tot != n - 1) {
        puts("0");
        return 0;
    }
    each(i, n + 1)
        root[i] = i;
    range(i, 1, cnt)
    {
        sum = 0;
        dfs(i, segs[i].l, 0);
        ans = ans * sum % mod;
        range(j, segs[i].l, segs[i].r)
        {
            int ru = findRoot(edges[j].u), rv = findRoot(edges[j].v);
            if (ru != rv)
                root[rv] = ru;
        }
    }
    printf("%d\n", ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

最小生成树

HDU 4408 Minimum Spanning Tree

真是不容易啊…… 最小生成树计数,虽然说觉得以后已经基本不会考到了,但 Read more…

最小生成树

关于最小生成树计数算法的粗浅证明

问题描述 最小生成树计数问题是给定一个无向带权图,问你能生成最小生成树 Read more…

最小生成树

HDU4081 Qin Shi Huang’s National Road System

传送门 昨天第一次跟两个妹子一起打……真特么那个紧张啊 人生赢家请闭嘴 Read more…