[JSOI2008]最小生成树计数
Time Limit:1000MS Memory Limit:165536K
Total Submit:100 Accepted:38
Description
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
Input
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。
接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。
注意：具有相同权值的边不会超过10条。
Output
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
Sample Input
Sample Output
Source
这题是老题了。。本来想A掉爽一下的，结果WA半天，最后发现还可能有无生成树的情况囧。。。
。。算法的话很显然对于所有一组权值相同的边，它们以最大数量加入之后，造成的连通性是一样的，那么从小到大算出每一组边，乘起来就OK了。。
如果数据大一点的话只好用矩阵来算答案了。。不过这里范围这么小暴力就OK了。。。
Code：
#include <vector>
#include <iostream>
#include <map>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int mod=31011,maxn=100,maxm=1000;
using namespace std;
typedef pair<int,int> ii;
struct UF
{
int F[maxn];
void clear(){rep(i,maxn)F[i]=i;}
int find(int x)
{
if(F[x]==x)return x;
return F[x]=find(F[x]);
}
bool Union(int i,int j)
{
i=find(i);j=find(j);
return F[i]=j,i!=j;
}
UF& operator=(const UF&u)
{
memcpy(F,u.F,sizeof(F));
return *this;
}
};
int n,m,ans=1,get,ret;
typedef map<int,vector<ii> >::iterator mit;
map<int,vector<ii> > M;
UF All,Link;
vector<ii> now;
void Dfs(int p,int c)
{
if(p==now.size())
{
if(c==get)ret++;
return;
}
ii t=now[p];UF tmp=Link;
if(Link.Union(t.first,t.second))Dfs(p+1,c+1);
Link=tmp;
Dfs(p+1,c);
}
int main()
{
cin>>n>>m;int s,t,c;
rep(i,m)
{
cin>>s>>t>>c;s–;t–;
M.pb(ii(s,t));
}
All.clear();s=0;
for(mit i=M.begin();i!=M.end();i++)
{
now=i->second;Link=All;get=0;ret=0;
rep(j,now.size())get+=All.Union(now[j].first,now[j].second);
Dfs(0,0);ans*=ret;ans%=mod;s+=get;
}
if(s<n-1)cout<<0<<endl;
else cout<<ans<<endl;
}
84 61 2 11 3 11 4 12 3 22 4 13 4 1
