题解 [ABC328E] Modulo MST

· · 题解

不是很难的 ABC E，甚至相比于以前的简单。

题意

给你一个 N 个点 M 条边的图，求出这个图在模 K 意义下的最小生成树。

分析

观察到数据范围其实很小，所以先从朴素算法开始分析，考虑直接枚举子集。

但是每个子集组成的边不一定是一棵树，一棵树显然要满足任意两个点之间有且只有一条边连接。

所以枚举边集有且仅能有 N-1 个元素，且连接后仅有一个连通块，这个并查集处理即可。

所以时间复杂度是 O(nC_m^{n-1})，但是因为本人懒得写搜索直接用的枚举二进制位。

代码

//the code is from chenjh
#include<cstdio>
#include<algorithm>
typedef long long LL;
int n,m;
LL k;
struct Edge{
    int u,v;
    LL w;
}e[30];
int f[10];
int fd(const int x){return x==f[x]?x:f[x]=fd(f[x]);}//并查集路径压缩找根。
int main(){
    scanf("%d%d%lld",&n,&m,&k);
    for(int i=0;i<m;i++) scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
    LL s=k;
    for(unsigned int x=0,mx=1u<<m;x<mx;x++)if(__builtin_popcount(x)==n-1){//判断是否刚好选了 n-1 条边。
        f[1]=1,f[2]=2,f[3]=3,f[4]=4,f[5]=5,f[6]=6,f[7]=7,f[8]=8;//对并查集进行初始化，循环展开加快速度。
        bool sol=1;LL w=0;
        int g=n;//连通块数量。
        for(int i=0;i<m;i++)if((x>>i)&1){
            if(fd(e[i].u)==fd(e[i].v)){sol=0;break;}//每两点之间有且仅有一条路径，如果已经连接说明不合法。
            f[fd(e[i].u)]=fd(e[i].v),--g;//成功合并一次减少一个连通块。
            w=(w+e[i].w)%k;
        }
        if(sol && g==1) s=s<w?s:w;//合法就取最小值。
    }
    printf("%lld\n",s);
    return 0;
}