广义串并联图方法
stripe_python · · 算法·理论
引入
回想物理中的电路模型。
- 对于两个串联电阻
R_1,R_2 ,可以将其等效为R_1+R_2 。 - 对于两个并联电阻
R_1,R_2 ,可以将其等效为\dfrac{R_1R_2}{R_1+R_2} 。
对一个电路图不断执行上述操作,似乎可以得到整个电路的等效电阻。
我们发现这个操作会在这种电路图上失效:
广义串并联图
广义串并联图,GSPG,定义是不存在同胚于
- 广义串并联图的树宽和分支宽至多为
2 。 - 因为广义串并联图不存在同胚于
K_4 的子图,自然也不可能包好同胚于K_5 或K_{3,3} 的子图。由 Kuratowski 定理,GSPG 必为平面图。 - 广义串并联图必能
3 染色。
在 OI 中,我们最常用的是广义串并联图方法。
- Compress / 缩二度点 / 消串联:删去一个二度点,将两端的点建新边。
- Twist / 叠重边 / 消并联:将两条重边叠合成一条。
- Rake / 删一度点 / 去断路:删去一个一度点与其出边。
如果图是广义串并联图,则可以通过如上三种操作缩为单点。对于一般图,若
实现时,我们用 std::map 维护邻接矩阵,用队列维护度数
使用广义串并联图方法的题,难点主要在于设计 DP 状态,并讨论三种操作时 DP 值转移的等效性。
P6790 [SNOI2020] 生成树
给出一张
n 个点m 条边的无向连通图,保证G 在删去某条边后是仙人掌。求G 的生成树数目,对998244353 取模。
:::::success[题解]
我们声称
设计 DP 状态为
- Rake:孤立边必选,将
f_e 乘进答案。 - Compress:边
e_1,e_2 至少有一条在生成树上,对于等效边e 满足 -
- Twist:边
e_1,e_2 不能同时在生成树上, 对于等效边e 满足 -
:::::
:::::info[代码]
const int N = 2e5 + 5;
int n, m; mint ans = 1;
struct node {mint f, g;};
node rake(const node& a, const node& b) {
return {a.f * b.g + b.f * a.g, a.g * b.g};
}
node compress(const node& a, const node& b) {
return {a.f * b.f, a.f * b.g + b.f * a.g};
}
void twist(const node& a) {ans *= a.f;}
map<int, node> e[N];
void add(int u, int v, const node& a) {
if (u == v) return ans *= a.g, void();
if (e[u].count(v)) {
node b = rake(e[u][v], a);
e[u][v] = e[v][u] = b;
} else {
e[u][v] = e[v][u] = a;
}
}
queue<int> q;
bool inq[N], vis[N];
void work() {
auto chk = [](int u) -> void {
if (!vis[u] && !inq[u] && e[u].size() <= 2) q.emplace(u), inq[u] = true;
};
for (int i = 1; i <= n; i++) chk(i);
while (!q.empty()) {
int u = q.front(); q.pop(), inq[u] = false;
if (vis[u]) continue;
if (e[u].size() == 0) {
vis[u] = true; continue;
}
if (e[u].size() == 1) { // twist
auto [v, a] = *e[u].begin();
twist(a), e[v].erase(u), e[u].clear(), vis[u] = true, chk(v);
} else { // compress
auto [v, a] = *e[u].begin();
auto [w, b] = *e[u].rbegin();
node c = compress(a, b);
e[v].erase(u), e[w].erase(u), e[u].clear(), vis[u] = true;
add(v, w, c), chk(v), chk(w);
}
}
}
void _main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
add(u, v, node{1, 1});
}
work(); cout << ans;
}
:::::
QOJ9278 Linear Algebra Intensifies
维护一个
n \times n 的矩阵A 。m 次操作给出l,r ,对所有i \in [l,r], j \in [l,r] ,令A_{i,j} \gets A_{i,j}+1 。操作结束后求\det A \bmod 998244353 。
:::::success[题解]
结论 行列式在二维差分后不变。
对矩阵
观察 Matrix-Tree 定理的形式,发现度数矩阵减邻接矩阵的系数正好对上,将问题转化为连边
建图以后,使用和上一题相同的广义串并联图方法,将问题规约到
考虑使用 Matrix-Tree 定理求子图生成树数目。我们要求的是
在
:::::
:::::info[代码]
const int N = 5e5 + 5;
int n, m, fa[N]; mint ans = 1;
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
struct node {mint f, g;};
node rake(const node& a, const node& b) {
return {a.f * b.g + b.f * a.g, a.g * b.g};
}
node compress(const node& a, const node& b) {
return {a.f * b.f, a.f * b.g + b.f * a.g};
}
void twist(const node& a) {ans *= a.f;}
map<int, node> e[N];
void add(int u, int v, const node& a) {
if (u == v) return ans *= a.g, void();
if (e[u].count(v)) {
node b = rake(e[u][v], a);
e[u][v] = e[v][u] = b;
} else {
e[u][v] = e[v][u] = a;
}
}
queue<int> q;
bool inq[N], vis[N];
void work() {
auto chk = [](int u) -> void {
if (!vis[u] && !inq[u] && e[u].size() <= 2) q.emplace(u), inq[u] = true;
};
for (int i = 0; i <= n; i++) chk(i);
while (!q.empty()) {
int u = q.front(); q.pop(), inq[u] = false;
if (vis[u]) continue;
if (e[u].size() == 0) {
vis[u] = true; continue;
}
if (e[u].size() == 1) { // twist
auto [v, a] = *e[u].begin();
twist(a), e[v].erase(u), e[u].clear(), vis[u] = true, chk(v);
} else { // compress
auto [v, a] = *e[u].begin();
auto [w, b] = *e[u].rbegin();
node c = compress(a, b);
e[v].erase(u), e[w].erase(u), e[u].clear(), vis[u] = true;
add(v, w, c), chk(v), chk(w);
}
}
}
int mp[N];
void _main() {
cin >> n >> m; iota(fa, fa + n + 1, 0);
for (int i = 1, l, r; i <= m; i++) {
cin >> l >> r;
add(l - 1, r, node{1, 1});
fa[find(l - 1)] = find(r);
}
int cnt = 0;
for (int i = 0; i <= n; i++) if (i == find(i)) cnt++;
if (cnt > 1) return cout << 0, void();
work(), iota(fa, fa + n + 1, 0);
for (int u = 0; u <= n; u++)
if (!vis[u]) for (auto [v, a] : e[u]) {
if (u < v && a.g == 0) {
if (find(u) == find(v)) return cout << 0, void();
fa[find(u)] = find(v), ans *= a.f;
}
}
int k = 0;
for (int i = 0; i <= n; i++) if (!vis[i] && i == find(i)) mp[i] = k++;
for (int i = 0; i <= n; i++) if (!vis[i]) mp[i] = mp[find(i)];
if (k == 0) return cout << ans, void();
matrix<mint, 600> L;
for (int u = 0; u <= n; u++)
if (!vis[u]) for (auto [v, a] : e[u]) {
if (u > v || a.g == 0) continue;
ans *= a.g;
if (mp[u] == mp[v]) continue;
mint w = a.f / a.g;
int i = mp[u], j = mp[v];
L[i][i] += w, L[j][j] += w, L[i][j] -= w, L[j][i] -= w;
}
cout << ans * L.det(k - 1);
}
:::::