[JSOI2008]最小生成树计数

题意

求一张图不同的的最小生成树个数，对31011取模，满足\(n\leq 100,m\leq 1000,w\leq 1e9\) 且每种边权的边数不超过10

思路

定理：对于不同的最小生成树方案，相同边权的边数不变

证明（伪）：假设比当前权值小的边都选择完了（不一定加进了最小生成树），那么当前权值为\(w\)的边一定要尽量的选，合并越多连通块越好。于是假设将当前权值的所有边加入可以合并\(k\)次连通块，由于有没有用的边存在，我们会将它们删掉，但仍然一定会保证这\(k\)次连通块合并仍然存在（前面说的加边越多越好），由于选择一条边即表示合并一次连通块，所以会选择\(k\)条边，显然这是一个定值

备注：其实从上面的证明中容易发现，\(k\)条边的一种合理选择方案所影响的连通块应该是一致的（只要有一种方案使得\(a\)与\(b\)相连，即使其他方案选择的边不同，也都会使\(a\)与\(b\)相连）

于是，我们求出最小生成树中有权值相同的边的个数，对于每一种权值，我们对其进行dfs，找到k条有用的边，这样算作一种方案，由于权值相同的边不会超过10，所以复杂度不超过\(2^{10}\)

时间复杂度为\(O(2^{10}m)\)

Code

#include<bits/stdc++.h>
#define N 1005
using namespace std;
const int mod = 31011;

int n,m,fa[N];
struct E {int u,v,w;} e[N];
struct Rgb {int l,r,v;} rgb[N];
int cnt,ans=1,sum,tot;

template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
bool cmp(E a,E b) {return a.w<b.w;}
int find(int x) {return fa[x] == x ? x : find(fa[x]);}
void kruskal()
{
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;++i)
    {
        if(e[i].w!=e[i-1].w) rgb[++cnt]=(Rgb){i,i,0};
        else rgb[cnt].r=i;
        int fx=find(e[i].u),fy=find(e[i].v);
        if(fx!=fy)
        {
            fa[fx]=fy;
            rgb[cnt].v++;
            tot++;
        }
    }
}
void dfs(int choose,int col,int now)
{
    if(now==rgb[col].r+1)
    {
        if(choose==rgb[col].v) ++sum;
        return;
    }
    dfs(choose,col,now+1);
    if(choose<rgb[col].v) 
    {
        int fx=find(e[now].u),fy=find(e[now].v);
        if(fx!=fy)
        {
            fa[fx]=fy;
            dfs(choose+1,col,now+1);
            fa[fx]=fx;fa[fy]=fy;
        }
    }
}
int main()
{
    read(n);read(m);
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i) read(e[i].u),read(e[i].v),read(e[i].w);
    kruskal();
    if(tot<n-1) {cout<<0<<endl;return 0;}
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=cnt;++i)
    {
        sum=0;
        dfs(0,i,rgb[i].l);
        ans=ans*sum%mod;
        for(int j=rgb[i].l;j<=rgb[i].r;++j)
        {
            int fx=find(e[j].u),fy=find(e[j].v);
            if(fx!=fy) fa[fx]=fy;
        }
    }
    cout<<ans<<endl;
    return 0;
}

[JSOI2008]最小生成树计数

原文：https://www.cnblogs.com/Chtholly/p/11426256.html