总结：此类题需要耐心观察规律，大胆猜想，然后证明猜想，得到有用的性质，然后解答。 简单的说：找隐含性质。
传送门：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; }