bzoj 1016 JSOI2008 最小生成树计数

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

我都不忍心吐槽了。

这么水的暴力我一开始竟然想写链剖！！！

对于某个权值，相同的边不会超过10条。于是，暴力，然后乘起来。

注意特判！特判！图不连通的时候输出0。

我的程序在不联通的时候会输出奇怪的数字……要崩溃了……

上代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#define N 111
#define M 1011
#define yu 31011
#define inf 0x7f7f7f7f
using namespace std;

struct sss
{
    int x, y;
    int val;
}bian[M];
int n, m;
int fa[N];
int use[M] = {0}, same[15], samenum = 0;
long long ans = 1, minval;

bool cmp(sss x, sss y) { return x.val < y.val; }

int find(int x)
{
    if (fa[x] == x) return x;
    fa[x] = find(fa[x]);
    return fa[x];
}

long long kru()
{
    long long nowval = 0; int nowc = n;
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        int x = find(bian[i].x);
        int y = find(bian[i].y);
        if (use[i] == 1 && x == y) return 0; // use[i] == 1 用 2 不用 
        if (use[i] == 2) continue;
        if (x != y)
        {
            fa[x] = y;
            nowval += bian[i].val;
            nowc --;
        }
    }
    if (nowc != 1) return 0;
    else return nowval;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d", &bian[i].x, &bian[i].y, &bian[i].val);
    sort(bian+1, bian+1+m, cmp);
    bian[0].val = -inf; bian[m+1].val = -inf;
    minval = kru();
    if (minval == 0)
    {
        printf("0\n");
        return 0;
    }
    for (int w = 1; w <= m; ++w)
    {
        samenum = 0;
        if (bian[w].val != bian[w+1].val) continue;
        same[++samenum] = w++;
        while (bian[w].val == bian[w-1].val) {same[++samenum] = w++;}
        w--;
        int zans = 0;
        int cou = (1 << samenum)-1;
        for (int i = 0; i <= cou; ++i)
        {
            int j = i, thisb = 1;
            for (int k = 1; k  <= samenum; ++k) use[same[k]] = 2;
            while (j){if (j & 1) use[same[thisb]] = 1;j >>= 1; thisb++;}
            if (kru() == minval) zans++;
        }
        for (int i = 1; i <= samenum; ++i) use[same[i]] = 0;
        ans *= (zans%yu);
        ans %= yu;
    }
    printf("%lld\n", ans%yu);
    return 0;
}