BZOJ1016: [JSOI2008]最小生成树计数【Kruskal】

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

【题目描述】

传送门

【题解】

这道题用到了最小生成树的几个性质。
第一,最小生成树每种边权的边数量一定。
第二(由第一点可得),当一个图有多个最小生成树时,只可能由一条边替换掉一条等边权的边来得到一颗新的最小生成树。
(摘自某dalao的博客)

我们注意到题目中有一个很重要的条件就是“具有相同权值的边不会超过10条”,我们就可以更具以上两条性质,暴力枚举当前选择权值为W的边,然后Kruskal就可以了。
复杂度O(2^{10} * m^2 * log_2(n))因为还有并查集的复杂度。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=105,MAXM=1005,MOD=31011;
int n,m,Ans=1,tot,Sum,V,fa[MAXN],P[MAXM],hsh[MAXM];
bool vis[MAXM];
struct xcw{
    int x,y,w;
    bool operator <(const xcw b)const{return w<b.w;}
}a[MAXM];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
void Kruskal(){
    tot=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int fx=get(a[i].x),fy=get(a[i].y);
        if(fx==fy) continue;
        fa[fy]=fx;V+=a[i].w;tot++;hsh[P[i]]++;
    }
}
void Work(){
    tot=0;int Now=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    if(vis[i]){
        int fx=get(a[i].x),fy=get(a[i].y);
        if(fx==fy) continue;
        fa[fy]=fx;Now+=a[i].w;tot++;
    }
    if(tot==n-1&&Now==V) Sum++;
}
void DFS(int Num,int Now,int R){
    if(Now>R){if(Num==0) Work();return;}
    vis[Now]=0,DFS(Num,Now+1,R);
    vis[Now]=1,DFS(Num-1,Now+1,R);
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
    sort(a+1,a+1+m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){P[i]=i;if(a[i].w==a[i-1].w) P[i]=P[i-1];}
    Kruskal();
    if(tot!=n-1){printf("0\n");return 0;}
    for(int i=1;i<=m;i++) vis[i]=1;
    for(int i=1,j;i<=m;i=j){
        j=i+1;
        while(P[i]==P[j]&&j<=m) j++;
        Sum=0;DFS(hsh[P[i]],i,j-1);if(Sum) Ans=(Ans*Sum)%MOD;
    }
    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部