题目大意
求一个加权无向图的最小生成树的个数。1<=n<=100; 1<=m<=1000，具有相同权值的边不会超过10条。
题解
命题1 由构成最小生成树的边的边权从小到大排序后得到的序列是唯一的。
证明：首先，改变边权为同一个$w$的边的排列顺序进行Kruskal会得到所有的最小生成树。对于一个边权$w$，令顺序改变前树中边权等于$w$的边集为$A$，顺序改变后树中边权等于$w$的边集为$B$，所有最小生成树中边权小于$w$的边的集合为$C$。若$|B|<|A|$，这意味着存在至少一条边$e\in B$，存在一个边集$D\subseteq A, |D|>1$，使得$\forall e\in D$，$D+C+\{e\}$中存在环。环的传递性是指：若$E$中无环，$\{e_1\}+E$中有环，在环内的边集为$E_1$，$\{e_2\}+E$中也有环，在环内的边集为$E_2$，则$\{e_1\}+\{e_2\}+E-E_1\times E_2$中也存在环。因此，元素个数至少为2的边集中$D$中必然存在环，为不可能现象。同理，$|B|>|A|$时，将$A,B$交换，也成立因此原命题成立。
命题2 对于一个不一定为连通图的图，定义它的连通性不变，当且仅当对于图中的每一个节点，与它连通的点的集合都不变。对于任意一个最小生成树，若将其中所有边权大于等于$w$的边都删除，则得到的子图的连通性对任意一个最小生成树来说都是相同的。
证明：本命题用数学归纳法证明比较清晰。当$w=0$时，树中没有任何边，显然命题成立。当$w-1$成立时，如果命题不成立，即所有边权等于$w$的边集$A$的排列顺序不同时，图的连通性不同，那么由连通性的定义，存在一对点$u,v$，使得Kruskal枚举到边权$w-1$时它们不连通，且边权枚举到$w$时，排序方式1使得$u, v$连通，排序方式2使得$u, v$不连通，那么排序方式2的情况是肯定不存在的，因为排序方式2中也会枚举到排列方式1中使$u, v$连通的边的，这条边没有理由不加入图中。因此，原命题成立。
上面的命题说明，不同的最小生成树的差别就在于边权相等的边集内选哪个了。题目说具有相同权值的边不会超过10条，所以我们先总体Kruskal看看对于每个边权都用到了多少条边，随后在一个个边权相等的边集中枚举组合即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; const int MAX_NODE = 110, MAX_EDGE = 1010, P = 31011;
int EWCnt[MAX_EDGE], EWIntreeCnt[MAX_EDGE];
long long Ans; struct Node
{
Node *PrevFather, *Father;
}_nodes[MAX_NODE];
int TotNode; struct Edge
{
Node *From, *To;
int Weight; bool operator < (const Edge& a) const
{
return Weight < a.Weight;
}
}_edges[MAX_EDGE];
int TotEdge; struct Discretion
{
private:
int OrgData[MAX_EDGE], Rank[MAX_EDGE];
int N; int LowerBound(int k)
{
int l = 1, r = N;
while (l < r)
{
int mid = (l + r) / 2;
if (k <= OrgData[mid])
r = mid;
else
l = mid + 1;
}
return l;
} public:
void Push(int val)
{
OrgData[++N] = val;
} void Init()
{
sort(OrgData + 1, OrgData + N + 1);
OrgData[0] = -1;
int curRank = 0;
for (int i = 1; i <= N; i++)
Rank[i] = OrgData[i] == OrgData[i - 1] ? curRank : ++curRank;
} int GetRank(int val)
{
return Rank[LowerBound(val)];
}
}d; void Read()
{
scanf("%d%d", &TotNode, &TotEdge);
for (int i = 1; i <= TotEdge; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
_edges[i].From = _nodes + u;
_edges[i].To = _nodes + v;
_edges[i].Weight = w;
}
} void Discrete()
{
for (int i = 1; i <= TotEdge; i++)
d.Push(_edges[i].Weight);
d.Init();
for (int i = 1; i <= TotEdge; i++)
{
_edges[i].Weight = d.GetRank(_edges[i].Weight);
EWCnt[_edges[i].Weight]++;
}
} void InitGraph()
{
for (int i = 1; i <= TotNode; i++)
_nodes[i].PrevFather = _nodes[i].Father = _nodes + i;
} Node *FindRoot(Node *cur)
{
return cur->Father == cur ? cur : cur->Father = FindRoot(cur->Father);
} bool Join(Edge *e)
{
Node *root1 = FindRoot(e->From), *root2 = FindRoot(e->To);
if (root1 != root2)
{
root1->Father = root2;
return true;
}
else
return false;
} void Kruskal(int begin, int end, bool op)
{
for (int i = begin; i <= end; i++)
if (Join(_edges + i))
EWIntreeCnt[_edges[i].Weight] += op;
} void Fa_Prev_Cur()
{
for (int i = 1; i <= TotNode; i++)
_nodes[i].Father = _nodes[i].PrevFather;
} void Fa_Cur_Prev()
{
for (int i = 1; i <= TotNode; i++)
_nodes[i].PrevFather = _nodes[i].Father;
} int DoSth(vector<int>& chosen, int k)
{
Fa_Prev_Cur();
for (int i = 0; i < chosen.size(); i++)
if (!Join(_edges + k + chosen[i] - 1))
return 0;
return 1;
} int Combination(vector<int>& chosen, int n, int m, int begin, int k)
{
chosen.push_back(begin);
m--;
int ans = 0;
if (n - begin < m);
else if (m == 0)
ans = DoSth(chosen, k);
else
for (int i = begin + 1; i <= n; i++)
ans += Combination(chosen, n, m, i, k);
chosen.pop_back();
return ans;
} int Combination(int n, int m, int k)
{
int ans = 0;
static vector<int> chosen;
for (int i = 1; i <= n - m + 1; i++)
ans += Combination(chosen, n, m, i, k);
return ans;
} int GetAns()
{
int cur = 1;
Ans = 1;
while (cur <= TotEdge)
{
int curW = _edges[cur].Weight;
int cnt = Combination(EWCnt[curW], EWIntreeCnt[curW], cur);
Ans = Ans * (cnt + (cnt == 0)) % P;
Kruskal(cur, cur + EWCnt[curW] - 1, false);
Fa_Cur_Prev();
cur += EWCnt[curW];
}
return (int)Ans;
} bool NotConnect()
{
Node *root = FindRoot(_nodes + 1);
for (int i = 2; i <= TotNode; i++)
if (FindRoot(_nodes + i) != root)
return true;
return false;
} int main()
{
Read();
Discrete();
sort(_edges + 1, _edges + TotEdge + 1);
InitGraph();
Kruskal(1, TotEdge, true);
if (NotConnect())
{
printf("0\n");
return 0;
}
InitGraph();
printf("%d\n", GetAns());
return 0;
}