题解 P4208 【[JSOI2008]最小生成树计数】

UPD in 2020/12/26：更换了图床。

UPD in 2020/8/12：修改排版与一些语言。原来的真是太丑了。

题目要求求出最小生成树的个数。

看起来无从下手，连暴力也想不出来。

所以我们需要一个最小生成树的性质。

定理： 同一个图的每个最小生成树中，边权相等的边数量相等。

证明：（不严谨）

考虑kruskal算法的过程，先排序，后枚举所有边。

对于同一边权的边，如果两端点不属于同一个联通块，总会在最小生成树中加入该边。

操作等价于：加入所有同一边权的边，后消除其中所有的简单环。

发现消环操作不影响对于顶点的连通性，且消除一个简单环等价于删掉环中一条边。

所以，无论如何消环，最终剩余总边数一定。其他边权以此类推。

算法1.枚举

题目中限制条件：相等边权的边数不超过 10。

考虑先求最小生成树，然后对于最小生成树中出现的每种边权，用暴力枚举的方式统计在同一边权的边中选取哪几条也可保证最小生成树连通性。

举例说明：

这是一个图。

这是原图的某一个最小生成树。

加上原图上的所有边权为3的边，新图长这样：

于是你可以枚举任意不成环的三边，他们都可以形成一种最小生成树，例如以下两种：

对于任意一个边权均是如此，例如边权为 4：

枚举类似边权为 3 的情况，此处不再列举。

对于同一边权，极限 2^{10} 枚举，统计当前边权答案后 O(m) 枚举其他边权，乘法原理统计答案。

极限时间复杂度 O(2^{10}m)（不好表示就直接把枚举复杂度算进去了），且实际复杂度不可能达到此值，可以通过。

算法2.生成树计数

由定理以及枚举做法的启发，我们可以每次指定最小生成树中的一种边权。

不过，相较于枚举并判环，我们有更好的方法保证最小生成树的连通性。

将最小生成树上非该边权的边都加在一个新图上，利用并查集缩点。

之后将原图中边权为选定值的边都加在新图上，注意缩点后边的处理。

还用以前的例子说明：

对黑点以及黑边缩点：

直接对该新图求生成树个数，即可统计答案并保证连通性。

这样就可以统计出取同一权值边的方案个数。枚举每种边权利用乘法原理统计答案即可。

但是，由于生成树计数是 O(n^3) 的算法，乍眼一看复杂度逼近 O(m n^3)，是不可行的。

以下严谨证明复杂度为 O(n^3)。

首先容易发现，在一棵树上，每删除一条边会使连通块个数 +1。

设最小生成树上有 k 种边权，每种边权边数为 c_1 到 c_k。

对于第 i 种边权，每次删掉 c_i 条边，形成 c_i+1 个连通块，对新图求生成树个数时间为 O(c_i^3)。总时间 O(\sum\limits_{i=1}^k c_i^3)。

有不等式：

\sum_{i=1}^{k} c_i^3 \leq \left(\sum_{i=1}^k c_i\right)^3

证明可以直接把右边拆开，除了左边那些三次项还有一堆非负项。

注意到 \sum\limits_{i=1}^k c_i = n-1，于是复杂度 O(n^3)。

以下是算法 2 的代码。算法 1 的代码请参看其他题解。

另，由于本人使用的是最裸的辗转相除法行列式求值，所以复杂度是 O(n^3\log n)。使用一些其他技巧就能达到 O(n^3) 的效率，详情请查看其他行列式求值相关博客。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N=101,M=1001,MOD=31011;

//原图，边权离散化并按相等边权存储 
struct e
{
    int x,y,v;
} tp[M],mst[M];
vector<e> edge[M]; 
int cmp(e a,e b)
{
    return a.v<b.v;
}

bool is[M];

//并查集 
int bcj[N],bel[N];
void init(int a)
{
    for(int i=1;i<=a;i++) bcj[i]=i;
}
int rt(int a)
{
    if(bcj[a]==a) return a;
    return bcj[a]=rt(bcj[a]);
}
bool uni(int a,int b)
{
    int p=rt(a),q=rt(b);
    if(p==q) return true;
    bcj[p]=q;
    return false;
}

//三个矩阵 度数、邻接、基尔霍夫 
int n,deg[N][N],g[N][N],mat[N][N];

int treecnt()//生成树计数，辗转相除高斯消元 
{
    int i,j,k,ans=1;
    for(i=1;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            while(mat[j][i])
            {
                int div=mat[i][i]/mat[j][i];
                for(k=i;k<n;k++) mat[i][k]=(mat[i][k]-1ll*mat[j][k]*div%MOD+MOD)%MOD;
                swap(mat[i],mat[j]);
                ans*=-1;
            }
            if(mat[i][i]==0) return 0;
        }
        ans=1ll*ans*mat[i][i]%MOD;
    }
    return (ans+MOD)%MOD;
}

int main()
{
    int a,b,i,j,k,tl=0,tmp=0,cnt=0;
    scanf("%d%d",&a,&b);
    init(a);
    for(i=0;i<b;i++) scanf("%d%d%d",&tp[i].x,&tp[i].y,&tp[i].v);
    sort(tp,tp+b,cmp);

    //kruskal 
    for(i=0;i<b;i++)
    {
        if(tp[i].v!=tmp) tl++,tmp=tp[i].v;
        edge[tl].push_back(tp[i]);
        if(uni(tp[i].x,tp[i].y)) continue;
        is[tl]=1,mst[cnt]=tp[i],mst[cnt++].v=tl;
    }
    if(cnt!=a-1)
    {
        printf("0");
        return 0;
    }

    //统计答案 
    int ans=1;
    for(i=1;i<=tl;i++)
    {
        //如果最小生成树中没有用到此边权 
        if(!is[i]) continue;

        init(a);
        int siz=edge[i].size();
        n=0;

        //将生成树上的边全部连上并缩点
        for(j=0;j<cnt;j++)
        {
            if(mst[j].v==i) continue;
            uni(mst[j].x,mst[j].y);
        }
        for(j=1;j<=a;j++)
        {
            if(bcj[j]==j) bel[j]=++n;
        }
        for(j=1;j<=a;j++) bel[j]=bel[rt(j)];

        //将原图中此边权的边全部连上 
        for(j=0;j<siz;j++)
        {
            int bx=bel[edge[i][j].x],by=bel[edge[i][j].y];
            deg[bx][bx]++,deg[by][by]++;
            g[bx][by]++,g[by][bx]++;
        }

        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
                mat[j][k]=deg[j][k]-g[j][k];
        ans=ans*treecnt()%MOD;

        //删除连上的边 
        for(j=0;j<siz;j++)
        {
            int bx=bel[edge[i][j].x],by=bel[edge[i][j].y];
            deg[bx][bx]--,deg[by][by]--;
            g[bx][by]--,g[by][bx]--;
        }
    }
    printf("%d",ans);
    return 0;
}