我都不忍心吐槽了。
这么水的暴力我一开始竟然想写链剖！！！
对于某个权值，相同的边不会超过10条。于是，暴力，然后乘起来。
注意特判！特判！图不连通的时候输出0。
我的程序在不联通的时候会输出奇怪的数字……要崩溃了……
上代码：
#include#include #include #include #include #include #define N 111#define M 1011#define yu 31011#define inf 0x7f7f7f7fusing 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;}