注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1016][JSOI2008]最小生成树计数  

2015-01-29 17:56:32|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1016: [JSOI2008]最小生成树计数

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 3081  Solved: 1215
[Submit][Status]

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

4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1

Sample Output

8

Solution

将边先按权值排序,权值相等的边合在一起计算,最后根据乘法原理得出答案。

如果一条边能被加入到生成树中当且仅当这条边所连接的两个端点尚未联通。

对于同一组边,利用Matrix_Tree定理求每一组边能组成的生成树个数。


Matrix_Tree定理:
G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值


Kirchhoff矩阵:
当存在边x-y时,C[x][x]++,C[y][y]++,C[x][y]--,C[y][x]--;

关于行列式求法:
就是高斯消元以后,把主对角线上的一坨数都乘起来就是答案

Code

/**************************************************************
    Problem: 1016
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:992 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define p 31011
#define N 110
long long a[N][N],ans=1,st;
int n,m,fa[N],i,j,k,cnt,tot,et,la[N],vis[N],mat[N][N],q[1010],l,r,x,y;
struct E{int x,y,v;}tmp[1010],e[1010];
struct G{int to,nxt;}g[1010];
#define add(x,y) (g[++et]=(G){y,la[x]},la[x]=et)
bool operator<(const E&i,const E&j){return i.v<j.v;}
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9')if(ch==0)return 0;aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
#define swap(a,b) (st=a,a=b,b=st)
void work(long long s)
{
    int i,j,k;
    for(q[l=r=1]=s,vis[s]=1;l<=r;l++)
    for(i=la[q[l]];i;i=g[i].nxt)
    if(!vis[g[i].to])vis[q[++r]=g[i].to]=1;
    std::sort(q+1,q+1+r);
    for(i=1;i<=r;i++)
    for(j=1;j<=r;j++)a[i][j]=(mat[q[i]][q[j]]+p)%p;
    for(--r,i=1;i<=r&&a[i][i];ans=ans*a[i][i]%p,i++)
    for(j=i+1;j<=r;j++)
    while(a[j][i])
    {
        s=a[i][i]/a[j][i];
        for(k=i;k<=r;k++)a[i][k]=(a[i][k]-a[j][k]*s%p+p)%p,swap(a[i][k],a[j][k]);
        ans=(p-ans)%p;
    }
}
int main()
{
    for(n=F(),i=1;i<=n;i++)fa[i]=i;if(n==1)return puts("0"),0;
    for(m=F(),i=1;i<=m;i++)e[i]=(E){F(),F(),F()};
    for(std::sort(e+1,e+1+m),i=1;i<=m;i++)
    if(gf(e[i].x)!=gf(e[i].y))
    cnt++,fa[fa[e[i].x]]=fa[e[i].y];
    if(cnt<n-1)return puts("0"),0;
    for(i=1;i<=n;i++)fa[i]=i;
    for(i=1;i<=m;i=j+1)
    {
        for(tot=0,j=i;e[j].v==e[i].v&&j<=m;j++)
        if(gf(e[j].x)!=gf(e[j].y))tmp[++tot]=e[j];j--;
        for(et=0,k=1;k<=tot;k++)x=gf(tmp[k].x),y=gf(tmp[k].y),
        mat[x][y]--,mat[y][x]--,mat[x][x]++,mat[y][y]++,add(x,y),add(y,x);
        for(k=1;k<=tot;k++)if(!vis[gf(tmp[k].x)])work(fa[tmp[k].x]);
        for(k=1;k<=tot;k++)x=gf(tmp[k].x),y=gf(tmp[k].y),
        mat[x][y]++,mat[y][x]++,mat[x][x]--,mat[y][y]--,
        la[x]=la[y]=vis[x]=vis[y]=0;
        for(k=1;k<=tot;k++)if(gf(tmp[k].x)!=gf(tmp[k].y))fa[gf(tmp[k].x)]=gf(tmp[k].y);
    }
    printf("%lld\n",ans);
}
  评论这张
 
阅读(171)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018