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

ydc的博客

 
 
 

日志

 
 

bzoj1016  

2013-01-23 18:13:11|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

最小生成树计数

我们已经知道Kruskal做最小生成树是对的,所以回顾一下。

因为我们可以把不同的最小生成树理解为把边按照不同的顺序排序做kruskal。但是kruskal又要求按从小到大排所以能换顺序的只有权值相同的

然 后按权值分组,我们全部选了能够得到一个连通情况,接下来就枚举那些边选,如果这些边不构成环并且选了之后的联通情况跟全选一样,这就是对于这组边的一种 选法了吧。而判断连通情况是否一致只要看连通块个数即可,因为枚举到的连通情况肯定是全选了的情况的子集,只要个数一样就一定等价。

具体可看代码,还有实在不懂的可自行yy

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 110
#define MAXM 1010
#define MOD 31011
using namespace std;
struct node
{
    int a,b,dis;
    void Read(){  scanf("%d %d %d",&a,&b,&dis);  }
    friend bool operator < (const node &a,const node &b){  return a.dis<b.dis;  }
}edge[MAXM];
int father[MAXN],F1[MAXN],F2[MAXN],n,m,ans=1,sum;
int k1,k2;
bool use[MAXM],mark[MAXM];
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        edge[i].Read();
}
int Find(int p,int father[])
{
    if(father[p]==0)  return p;
    father[p]=Find(father[p],father);
    return father[p];
}
void dfs(int p,int l,int r)
{
    if(p>r)
    {
        for(int i=1;i<=n;i++)
            F2[i]=father[i];
        for(int i=l;i<=r;i++)
            if(use[i]==true)
            {
                int x=Find(edge[i].a,F2),y=Find(edge[i].b,F2);
                if(x==y)  return ;
                F2[y]=x;
            }
        k2=0;
        for(int i=1;i<=n;i++)
            k2=k2+(Find(i,F2)==i);
        if(k1==k2)  sum++;
        return ;
    }
    use[p]=false,dfs(p+1,l,r);
    use[p]=true,dfs(p+1,l,r);
}
void solve()
{
    sort(edge+1,edge+m+1);
    for(int i=1,j;i<=m;i++)
    {
        if(mark[i]==truecontinue;
        k1=0;
        for(int k=1;k<=n;k++)
            F1[k]=father[k];
        for(j=i;j<=m&&edge[j].dis==edge[i].dis;j++)
        {
            mark[j]=true;
            int x=Find(edge[j].a,F1),y=Find(edge[j].b,F1);
            if(x!=y)  F1[y]=x;
        }
        for(int k=1;k<=n;k++)
            k1=k1+(Find(k,F1)==k);
        dfs(i,i,j-1);
        ans=ans*sum%MOD,sum=0;
        for(int j=1;j<=n;j++)
            father[j]=F1[j];
    }
    k1=0;
    for(int i=1;i<=n;i++)
        k1=k1+(Find(i,father)==i);
    if(k1!=1)  ans=0;
}
int main()
{
    read();
    solve();
    printf("%d\n",ans);
    return 0;
}
?
  评论这张
 
阅读(524)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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