[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