【习题选讲】xza《Graph Theory》

思维

$TC10947-TwoSidedCards$

正-反，二元关系，想到正反面数字对应连边，每张卡都变成了一条有向边。

我们发现形成的图是一个环！！因为正反都是排列，每个数字的度数都是 2。

分环讨论，设当前环长度为 $L$，选了 $k$ 个数字，显然相邻的不能选，所以方案数就是 $C(L, 2k)$ 还要 $*2$。

背包合并。

$CF547D-Mike and Fish$

题解

和上一题有异曲同工之妙。行-列，想到二元关系，于是行列建点，每个点都变成了一条有向边。设红色表示入边，蓝色表示出边，我们要给边定向，使得新图每个点的入度出度之差不超过 1。

怎么做？考虑构造欧拉回路。复习一波欧拉回路的定义：欧拉回路是经过图 G 中所有边的回路。但目前二分图中有偶数个（一定是偶数个，因为保证有解）奇数度点。有奇数度点就很难处理！

可以将奇数度点两两配对（通过连一些无关紧要的辅助边），对于每个连通块选一个初始为奇数度的点跑（注意先跑辅助边），没有就跑初始为偶数度的点，欧拉回路红蓝染色，就很好写。

这个正确性比较显然：欧拉回路上每个点入度出度都想同，每个点连的辅助边最多 1 条，删去辅助边后仍能满足限制。

复习欧拉回路基本写法：套圈法，其实就是把不同的环连在一起，dfs 函数还是有不少细节的

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x) {
    vis[x] = 1;
    for (int i = lnk[x]; i; i = nxt[i]) {
        if (!mark[i]) {
            mark[i] = mark[i ^ 1] = 1;
            lnk[x] = nxt[i];  // 当前弧优化
            dfs(to[i]);
            stk[++top] = id[i];
            i = lnk[x];  // !!!
        }
    }
}

$TC12330-CoinsGame$

假装你已经知道这是“等价类”的题目。考虑两个格子等价，当且仅当任意操作后原本在两个格子上的硬币要么同时在棋盘上，要么同时移出了棋盘，那么合法的方案至少有一个这样的格子对。

发现正做很难，考虑补集转化。发现等价的关系是可以传递的，那么就形成了很多个团。等价关系可以 bfs 找，并查集维护。用总方案减去只选这些团的方案数就好了。

$CF19E-Fairy$

很好的题。

对于环的题目，可以考虑 dfs 树，因为有个很优的性质：所有环在 dfs 树上的体现就是 树边 + 返祖边（没有横叉边，因为是 dfs 树）

而环到 {返祖边集合} 是单射

设奇环数为 $x$

  • $x = 0$，删任何一条边都可以
  • $x = 1$，只能删奇环上的边
  • $x > 1$，不能删返祖边。考虑所有的树边，能被删掉当且仅当所有的奇环经过了它且没有偶环经过它

树上差分就好了。