@codeforces - 1221G@ Graph And Numbers

左手的ㄟ右手 2023-06-01 14:56 6阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定一个 n 点 m 边的无向图。

现在要求给每个点写上 0 或 1，一条边的权值定义为该边连接的两点权值之和。

有多少种方案，使得存在至少一条边的权值为 0，至少一条边权值为 1，至少一条边权值为 2。

**Input**  
第一行包含两个数 n 和 m (1≤n≤40, 0≤m≤n\*(n−1)/2)，表示点数与边数。  
接下来 m 行，每行两个整数 xi 与 yi (1≤xi,yi≤n, xi≠yi)，描述一条边的两个端点。  
保证无重边。

**Output**  
输出合法的方案个数。

**Examples**  
**input**  
6 5  
1 2  
2 3  
3 4  
4 5  
5 1  
**output**  
20

**input**  
4 4  
1 2  
2 3  
3 4  
4 1  
**output**  
4

## @solution@ ##

n <= 40 暗示 meet in the middle。要求的计数方案暗示容斥。

首先考虑怎么容斥，我们统计以下方案数量：  
f1：没有任何限制。  
f2：强制 0 不出现。  
f3：强制 1 不出现。  
f4：强制 2 不出现。  
f5：强制 0 与 1 不出现。  
f6：强制 0 与 2 不出现。  
f7：强制 1 与 2 不出现。  
f8：强制 0, 1 与 2 不出现。  
最终答案 ans = f1 - f2 - f3 - f4 + f5 + f6 + f7 - f8。

接下来考虑具体怎么计数。  
首先易得 f1 = 2^n。  
如果所有连通分量大小都为 1，共有 m 个连通分量，则 f8 = 2^m；否则 f8 = 0。  
如果所有连通分量都为二分图，共有 m 个连通分量，则 f6 = 2^m；否则 f6 = 0。  
如果大小为 1 的连通分量个数为 k，则 f5 = f7 = 2^k。  
如果总连通分量个数为 m，则 f3 = 2^m。

而剩下的 f2， f4 就需要双向搜索。因为 f2 = f4，我们不妨只考虑 f4。  
假如点 u 的数值为 0，则它相邻的点不带限制；否则如果点 u 的数值为 1，它相邻的点只能为 0。

我们枚举前一半的二进制状态，得到哪些点必须为 0，进而判断当前状态是否合法。  
记 f\[s\] 表示 s 是否合法，合法为 1，否则为 0；g\[s\] 表示二进制 s' <= s 的 f\[s'\] 之和，高维前缀和即可。

查询时枚举后一半的二进制状态，首先判断是否合法，然后得到前一半哪些为 0，哪些为 0 或 1。直接取 g 值即可。

## @accepted code@ ##

#include<cstdio> #include<queue> using namespace std; typedef long long ll; int n, m; ll G[40 + 5]; int fa[40 + 5], siz[40 + 5]; int find(int x) { return fa[x] = (fa[x] == x ? x : find(fa[x])); } void unite(int x, int y) { int fx = find(x), fy = find(y); if( fx != fy ) fa[fx] = fy, siz[fy] += siz[fx]; } ll check(int x) { ll d[40 + 5] = {}; for(int i=0;i<n;i++) d[i] = -1; queue<int>que; que.push(x); d[x] = 0; while( !que.empty() ) { int f = que.front(); que.pop(); for(int i=0;i<n;i++) if( (G[f]>>i) & 1 ) { if( d[i] == -1 ) { d[i] = d[f] ^ 1; que.push(i); } else { if( d[i] != (d[f] ^ 1) ) return 0; } } } return 2; } ll solve1() { ll ret1 = 1, ret2 = 1, ret3 = 1, ret4 = 1; for(int i=0;i<n;i++) if( fa[i] == i ) { ret1 <<= 1; ret2 = ret2*check(i); ret3 = (siz[i] == 1) ? (ret3<<1) : ret3; ret4 = (siz[i] == 1) ? (ret4<<1) : 0; } return ret2 - ret1 + (ret3<<1) - ret4; } ll f[1<<20]; void dfs1(int d, int mxd, int s1, int s2) { if( d == mxd ) { f[s1]++; return ; } dfs1(d + 1, mxd, s1, s2); if( !(s2 & (1LL<<d)) ) dfs1(d + 1, mxd, s1|(1LL<<d), s2|G[d]); } int mid, t; ll dfs2(int d, int mxd, ll s) { if( d == mxd ) { s = s & t, s = s ^ t; return f[s]; } ll ret = dfs2(d + 1, mxd, s); if( !(s & (1LL<<d)) ) ret += dfs2(d + 1, mxd, s|G[d]); return ret; } ll solve2() { mid = (n>>1), t = (1<<mid) - 1; dfs1(0, mid, 0, 0); for(int i=0;i<mid;i++) for(int j=0;j<=t;j++) if( j & (1LL<<i) ) f[j] += f[j^(1LL<<i)]; return dfs2(mid, n, 0); } int main() { scanf("%d%d", &n, &m); for(int i=0;i<n;i++) fa[i] = i, siz[i] = 1; for(int i=1;i<=m;i++) { int x, y; scanf("%d%d", &x, &y), x--, y--; G[x] |= (1LL<<y), G[y] |= (1LL<<x), unite(x, y); } printf("%lld\n", (1LL<<n) + solve1() - (solve2()<<1)); }

## @details@ ##

一开始没有考虑到连通块大小为 1（即该连通块中没有边）的情况，WA 了一次。

然后因为没开 long long，WA 了好几次。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11568191.html