最小生成树计数
题目描述
现在给出了一个简单无向加权图.你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树.(如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的).由于不同的最小生成树可能很多,所以你只需要输出方案数对$31011$的模就可以了.
输入
第一行两个数$n$和$m$,其中$1\le n\le 100,1\le m\le 1000$,分别表示无向图的节点数和边数.每个节点用$1 \ldots n$的整数编号.接下来$m$行,每行三个整数$a,b,c$表示节点$a$与节点$b$之间有一条权值为$c$的边.$1\le c\le 1 \times 10^9$.保证没有自环或重边. //$c$相同的边不超过$10$条.
输出
输出不同的最小生成树有多少个.你只需要输出数量对$31011$的模就可以了.
样例
IN
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
OUT
8
大家应该都知道Kruskal吧...还是稍微提一下好了.
Kruskal是一种最小生成树算法,就是将途中所有边从小到大排序再挨个扫描,每扫描到一条新边时就查看下这条边连接的两端点是否属于同一个联通块,如果是的就不加进去,否则就加进去.大家可以认为这个算法是'显然正确'的.至于为什么是正确的呢,我的想法不够严谨,我就不拉出来献丑了.
好了,一条边被Kruskal选中是要拼RP的.也就是说,如果在sort时,一条边比另一条边拍得更前面,它选中的机率越大.
这时,如果我们将处理一个特定权值$n$的所有边看成一个阶段,这时我们先不要将这些边急着加进去,而是一起处理.具体方法就是设上一个阶段的生成森林为$F_L$,如果加进一条$n$的边使得$F_L$中的一棵树变成了仙人掌,我们就弃掉它[P].反之,将它加入一个临时图$T_N$中.阶段完成后,将$T_N$加入缩点后的$F_L$中,求它每个子联通块的生成树个数,相乘,再把这个结果和上一个阶段的结果相乘就是这个阶段的结果了.当然我们无需显式地缩点,我们只需要对联通块直接计算,因为我们将每个$F_L$联通块之内的边都去掉了[P].
具体细节很难想,不过是一道好题.比较有意思.注意每个阶段末要随便选择一种方案啊.
-------------------------------------------------------------
代码
(不会计算行列式怎么破= =)
int det(int a[][N],int n)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
a[i][j]%=mod;
int ret=1;
for(int i=1; i<n; i++)
{
for(int j=i+1; j<n; j++)
while(a[j][i])
{
int t=a[i][i]/a[j][i];
for(int k=i; k<n; k++)
a[i][k]=(a[i][k]-a[j][k]*t)%mod;
for(int k=i; k<n; k++)
swap(a[i][k],a[j][k]);
ret=-ret;
}
if(a[i][i]==0)
return 0;
ret=ret*a[i][i]%mod;
}
if(ret<0)
ret=-ret;
return (ret+mod)%mod;
}
神奇的det算法...似乎也是高斯消元,怎么没有逆元?