题目描述

给定一个\(n\)个点，\(m\)条边的联通无向图，给每个点染上\(k\)中颜色中的一种（可以不用完\(k\)种颜色），且每条边所连接的两个的点颜色不同，求方案数（答案对\(1e9+7\)取模）

\(n \le 1e5, m \le n + 5, 3 \le k \le 1e5\)

解析

著名的\(NPC\)问题——图的\(m\)着色问题（GCP）……的弱化版

图的\(m\)着色问题的一种比较优秀的暴力算法是枚举划分，但是当点数过多时就不好用了

所以我们考虑能不能把原图等效成一张更小的图

我们给每条边两个权值\(a_i, b_i\)，分别表示当两个端点异色/同色时，这条边产生的贡献（这里“贡献”含义还比较模糊，结合下面缩图的过程比较好理解），一种染色方案的贡献就是图中每条边对应权值的乘积

显然，原图上每条边的\(a_i\)为\(1\)，\(b_i\)为\(0\)

接下来考虑缩图

• 对于度数为\(1\)的点\(u\)：
  • 设与它相邻的点为\(v\)
  • 可以直接删去\(u\)和边\((u, v)\)，同时将最终答案乘上\((k - 1)a_{(u, v)} + b_{(u, v)}\)
  • 因为\(v\)颜色确定时，\(u\)的颜色有\(k - 1\)种情况和它不同，\(1\)种情况和它相同
• 对于度数为\(2\)的点\(u\)：
  • 设与它相邻的两点为\(v1, v2\)，考虑把\(u\)并到\((v1, v2)\)上去
  • \(v1, v2\)异色时，\(u\)有\(k - 2\)种情况和它们均不同色，\(1\)种情况仅和\(v1\)同色，\(1\)种情况仅和\(v2\)同色
  • \(v1, v2\)同色时，\(u\)有\(k - 1\)种情况和它们均不同色，\(1\)种情况和它们同色
  • 所以\(a_{(v1, v2)}\)乘上\((k - 2) \cdot a_{(u, v1)} \cdot a_{(u, v2)} + b_{(u, v1)} \cdot a_{(u, v2)} + a_{(u, v1)} \cdot b_{(u, v2)}\)
  • \(b_{(v1, v2)}\)乘上\((k - 1) \cdot a_{(u, v1)} \cdot a_{(u, v2)} + b_{(u, v1)} \cdot b_{(u, v2)}\)
  • 这里注意如果原来没有\((v1, v2)\)这条边，新建的一条初始\(b\)为\(1\)，因为颜色可以相同

缩完图后，剩下的点度数都不小于\(3\)（或者只剩一个点），所以\(3n \le 2m\)，又根据\(m \le n + 5\)，有\(n \le 10, m \le 15\)

然后图就很小了，就可以枚举划分（第\(11\)个贝尔数不大，\(1e5\)左右）然后暴力累加贡献了，记得乘上度数为\(1\)的点的贡献

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define fst first#define scd second#define MAXN 100010typedef long long LL;typedef std::pair
         
           pii;const int mod = (int)1e9 + 7;struct Edge { int u, v; mutable int a, b; Edge(int _u = 0, int _v = 0, int _a = 0, int _b = 0) :u(_u), v(_v), a(_a), b(_b) {} bool operator <(const Edge &e) const { return u == e.u ? v < e.v : u < e.u; }};typedef std::set
          
           ::iterator iter;char gc();int read();void dfs(int, int);int N, M, K, bel[MAXN], deg[MAXN], x[MAXN], y[MAXN], ifact[MAXN], inv[MAXN], fact[MAXN], ans1 = 1, ans2 = 0;int que[MAXN], hd, tl;bool ban[MAXN], vis[MAXN];std::set
           
             edge;std::vector
            
              con[MAXN], node;inline void inc(int &x, int y) { x += y; if (x >= mod) x -= mod; }inline void dec(int &x, int y) { x -= y; if (x < 0) x += mod; }inline int add(int x, int y) { x += y; return x >= mod ? x - mod : x; }inline int sub(int x, int y) { x -= y; return x < 0 ? x + mod : x; }inline int mul(int x, int y) { return (LL)x * y % mod; }inline iter get_edge(int u, int v) { return edge.find(Edge(std::min(u, v), std::max(u, v))); }int main() { freopen("color.in", "r", stdin); freopen("color.out", "w", stdout); N = read(), M = read(), K = read(); fact[0] = ifact[0] = fact[1] = ifact[1] = inv[1] = 1; for (int i = 2; i <= K; ++i) { fact[i] = mul(fact[i - 1], i); inv[i] = sub(0, mul(mod / i, inv[mod % i])); ifact[i] = mul(ifact[i - 1], inv[i]); } for (int i = 1; i <= M; ++i) { x[i] = read(), y[i] = read(); if (x[i] > y[i]) std::swap(x[i], y[i]); ++deg[x[i]], ++deg[y[i]]; con[x[i]].push_back(y[i]); con[y[i]].push_back(x[i]); edge.insert(Edge(x[i], y[i], 1, 0)); } for (int i = 1; i <= N; ++i) if (deg[i] <= 2) que[tl++] = i, vis[i] = 1; while (hd < tl) { int p = que[hd++]; if (deg[p] == 0) continue; ban[p] = 1; if (deg[p] == 1) { for (int i = 0; i < con[p].size(); ++i) if (!ban[con[p][i]]) { int v = con[p][i]; iter it = get_edge(p, v); ans1 = mul(ans1, add(mul(K - 1, it->a), it->b)); edge.erase(it); if ((--deg[v]) <= 2 && !vis[v]) que[tl++] = v, vis[v] = 1; break; } } else { int v1 = 0, v2 = 0; for (int i = 0; i < con[p].size(); ++i) if (!ban[con[p][i]]) { if (!v1) v1 = con[p][i]; else { v2 = con[p][i]; break; } } if (v1 > v2) std::swap(v1, v2); iter it1 = get_edge(p, v1), it2 = get_edge(p, v2); iter nit = get_edge(v1, v2); if (nit == edge.end()) { nit = edge.insert(Edge(v1, v2, 1, 1)).first; con[v1].push_back(v2), con[v2].push_back(v1); ++deg[v1], ++deg[v2]; } nit->a = mul(nit->a, add(add(mul(it1->a, it2->b), mul(it1->b, it2->a)), mul(mul(it1->a, it2->a), K - 2))); nit->b = mul(nit->b, add(mul(it1->b, it2->b), mul(mul(it1->a, it2->a), K - 1))); edge.erase(it1), edge.erase(it2); if ((--deg[v1]) <= 2 && !vis[v1]) que[tl++] = v1, vis[v1] = 1; if ((--deg[v2]) <= 2 && !vis[v2]) que[tl++] = v2, vis[v2] = 1; } } for (int i = 1; i <= N; ++i) if (!ban[i]) node.push_back(i); dfs(0, 0); printf("%d\n", ans2); return 0;}inline char gc() { static char buf[1000000], *p1, *p2; if (p1 == p2) p1 = (p2 = buf) + fread(buf, 1, 1000000, stdin); return p1 == p2 ? EOF : *p2++;}inline int read() { int res = 0; char ch = gc(); while (ch < '0' || ch > '9') ch = gc(); while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + ch - '0', ch = gc(); return res;}void dfs(int k, int tot) { if (tot > K) return; if (k >= node.size()) { int tmp = 1; for (iter it = edge.begin(); it != edge.end(); ++it) if (bel[it->u] == bel[it->v]) tmp = mul(tmp, it->b); else tmp = mul(tmp, it->a); if (!tmp) return; inc(ans2, mul(ans1, mul(tmp, mul(fact[K], ifact[K - tot])))); } else { for (int i = 1; i <= tot; ++i) bel[node[k]] = i, dfs(k + 1, tot); bel[node[k]] = tot + 1, dfs(k + 1, tot + 1); }}//Rhein_E 100pts