[ABC294Ex] K-Coloring

本文主要是介绍[ABC294Ex] K-Coloring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

引

属于一眼题,不看时间限制 $8s$ 容易被诈骗

解法

简单容斥
大概 式子就是 $\sum (-1{)}^M\ast K^{|S|}$ , $M$ 为边集的大小， $|S|$ 为联通块的数量
那么我们就有 空间复杂度： $O(2^N)=1e9$ ,时间复杂度： $O(2^{N}M)$
1.用 $dfs$ 搜索所有的状态，可以省去开数组的空间
2.加上剪枝,当加入一条边后,图的连通性未改变，那么后继所有状态一定都会相互抵消,直接返回 $0$
加上两种优化后
空间复杂度： $O(1)$
时间复杂度： $O(2^N\ast 玄学)$

Code

#include <algorithm>
#include <iostream>using db = double;
using ll = long long;
using namespace std;const int N=37,mod=998244353;int n,m,k,p[N],u[N],v[N],fa[N];int find(int x) { return x==fa[x]?x:find(fa[x]); }int dfs(int i,int cnt) {if(i==m+1) return p[cnt];int x=find(u[i]),y=find(v[i]);if(x==y) return 0;int f1=dfs(i+1,cnt);fa[y]=x;int f2=dfs(i+1,cnt-1);fa[y]=y;return (f1-f2+mod)%mod;
} 
int main(){srand(998244353);scanf("%d%d%d",&n,&m,&k);p[0]=1; for(int i=1;i<=n;i++) p[i]=1ll*p[i-1]*k%mod,fa[i]=i;for(int i=1;i<=m;i++) {scanf("%d%d",&u[i],&v[i]);if(rand()%2) swap(u[i],v[i]);}printf("%d\n",dfs(1,n));
}

结

其实就是想记录一下优化的方法

这篇关于[ABC294Ex] K-Coloring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---