题解 P2143 【[JSOI2010]巨额奖金】

· · 题解

题意理解

要求任何两个区之间都可以只通过新型干道（直接或间接地）连接。

要求一个生成树(在一个环删去任意一条新型干道都满足以上条件)。

又因为要求费用最小。所以要求最小生成树。

于是我们就可以开始求最小生成树有多少种了。

思路

最小生成树的一个性质,多种最小生成树,任意一种相同边权的边选择的数量不变。(如果多选一个1个就构成环了,少选1个就不最优了。)。

此题数据有点水,所以我就用dfs过了。讲一下dfs的方法。

对边进行排序,找出所以边权一样的道路,然后暴力dfs有多少种方案能使其不构成环,且满足性质(题解思路的第1行提到)。

用乘法原理,将所有不同边权的答案乘起来,就是答案。

要注意的是,判断构不构成环要用到并查集。并查集千万不能路径压缩,因为我们回溯的时候要方便拆。

具体做法放在代码里了。时间复杂度为O(sum{k \times 2^k})。其中k为相同花费的边的数量。最坏时间复杂度为O(n×2^{m}),可以被一组所有边权都一样的数据卡掉。

AC代码

#include<iostream>
#include<algorithm>
using namespace std;
#define mod 31011
struct xyq{
    long long u,v,w; //u--w-->v(u到v有一条w的边。)。
}_[1000005];
struct rule{ //自定义排序。
    bool operator()(const xyq &s1,const xyq &s2){
        return s1.w<s2.w;
    }
};
long long f[1000005];
long long getfather(long long iakioi){ //并查集,找根节点。
    if(f[iakioi]==iakioi){
        return iakioi;
    }
    return getfather(f[iakioi]);
}
long long dfs(long long l,long long r,long long a){ //l~r的区间里选a条边。
    if(l>r){ //如果超过了。
        return (a==0); //返回是否选完了。
    }
    long long sum=0,i,f1,f2;
    f1=getfather(_[l].u);
    f2=getfather(_[l].v);
    if(f1!=f2){ //选的情况。必须不构成环才可以选。
        f[f1]=f2; //合并。
        sum+=dfs(l+1,r,a-1); //下一个,l要加一,由于选了,所以a(还需选多少个)要减一。
        f[f1]=f1; //由于没有路径压缩,所以直接取消就可以拆开。
    }
    sum+=dfs(l+1,r,a); //不选的情况,必须不过怎么样都可以不选,所以不需要if语句。
    return sum; 
}
long long l[1000005],size[1000005]; //size为应选边的条数。
void clearf(long long lid,long long rid){ //清空并查集。 
    long long i;
    for(i=lid;i<rid;++i){
        f[i]=i;
    }
}
int main(){
    long long n,m,i,j,a,b,c,ykb,f1,f2,tot=1,sum=0;
    cin>>n>>m;
    clearf(0,n);
    for(i=0;i<m;++i){
        cin>>_[i].u>>_[i].v>>_[i].w;
    }
    sort(_,_+m,rule()); //按改造道路的花费排序。
    for(i=0;i<m;++i){ //kruskal求最小生成树。
        f1=getfather(_[i].u);
        f2=getfather(_[i].v);
        if(f1!=f2){
            ++size[tot-1]; //记录下每种花费选了多少。
            f[f1]=f2;
            ++sum; //记录改造了多少条道路。
        }
        if(_[i].w!=_[i+1].w){
            l[tot]=i+1; //记录下每种花费开始的位置。
            ++tot;
        }
    }
    if(sum!=n-1){ //如果图不连通(即选不出一棵树),就直接输出0,不特判可能会WA。
        cout<<0;
        return 0;
    }
    sum=1; //注意乘法不要初始化为0,否则答案永远都是0。
    l[tot]=m+1;
    clearf(0,n); //kruskal将边都连起来了,dfs一开始什么边都没连,记得清空。
    for(i=0;i<tot;++i){
        sum=(sum*dfs(l[i],l[i+1]-1,size[i]))%mod; //从起始位置到结束(下一个起始位置-1),因为相同边权的边数量不变,所以枚举size[i]个。。。。。乘法原理,边乘边膜,防止爆。
        for(j=l[i];j<l[i+1];++j){ //合并,将所有这一次选的边在不构成环的情况下都合并。
            f1=getfather(_[j].u);
            f2=getfather(_[j].v);
            if(f1!=f2){ //没有环直接连接。
                f[f1]=f2;
            }
        }
    }
    cout<<sum%mod;
    return 0;
}

蒟蒻不会什么矩阵树,所以只写了dfs,虽然我是靠数据水通过的写的不是正解,但我希望大家都看懂了。没看懂可以在评论区问,我尽量回答。