Description
给定一个连通的带边权的图（允许自环和重边），求不同的最小生成树个数。两个生成树不同当它们所用的边的序号不同，换句话说，重边算多次。
Input
第一行n,m，表示点数和边数(1<=n<=50000,1<=m<=100000) 下接m行，每行3个数k1,k2,w，表示k1和k2之间有一条权值为w 的边。
Output
仅一行一个数：生成树个数 mod 1000003（质数）
Sample Input
3 5
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8
Sample Output
5
注：不会存在5条及5条以上的边，他们的边权是相同的。
样例解释：
5棵生成树分别如下（边按输入顺序标号）：
(1,3) (2,3) (1,4) (2,4) (3,4)
5号边是自环。
样例解释：
5棵生成树分别如下（边按输入顺序标号）：
(1,3) (2,3) (1,4) (2,4) (3,4)
5号边是自环。
HINT
Source
Solution
同$BZOJ1016$，感觉如果第一页那题能过，这题也能过。题解依然是我写的。
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int u, v, w, x;
inline bool operator< (const edge &rhs) const
{
return x < rhs.x;
}
}e[];
struct count
{
int l, r, use;
}g[];
int n, m, fa[], siz[]; int getfa(int x)
{
return fa[x] == x ? x : getfa(fa[x]);
} void link(int u, int v)
{
if(siz[u] > siz[v]) fa[v] = u, siz[u] += siz[v];
else fa[u] = v, siz[v] += siz[u];
} bool Kruskal()
{
int cnt = , u, v;
for(int i = ; i <= m; ++i)
{
u = getfa(e[i].u), v = getfa(e[i].v);
if(u != v)
{
link(u, v);
++g[e[i].w].use;
if(++cnt == n - ) return true;
}
}
return false;
} int DFS(int w, int i, int k)
{
if(k == g[w].use) return ;
if(i > g[w].r) return ;
int ans = , u = getfa(e[i].u), v = getfa(e[i].v);
if(u != v)
{
link(u, v);
ans = DFS(w, i + , k + );
fa[u] = u, fa[v] = v;
}
return ans + DFS(w, i + , k);
} int main()
{
int u, v, w, ans;
cin >> n >> m;
for(int i = ; i <= n; ++i)
fa[i] = i, siz[i] = ;
for(int i = ; i <= m; ++i)
{
cin >> u >> v >> w;
e[i] = (edge){u, v, , w};
}
sort(e + , e + m + );
w = ;
for(int i = ; i <= m; ++i)
if(e[i].x == e[i - ].x) e[i].w = w;
else
{
g[w].r = i - ;
e[i].w = ++w;
g[w].l = i;
}
g[w].r = m;
ans = Kruskal();
for(int i = ; i <= n; ++i)
fa[i] = i, siz[i] = ;
for(int i = ; i <= w; ++i)
{
ans = ans * DFS(i, g[i].l, ) % ;
for(int j = g[i].l; j <= g[i].r; ++j)
{
u = getfa(e[j].u), v = getfa(e[j].v);
if(u != v) link(u, v);
}
}
cout << ans << endl;
return ;
}