广义串并联图方法

· · 算法·理论

引入

回想物理中的电路模型。

对一个电路图不断执行上述操作,似乎可以得到整个电路的等效电阻。

我们发现这个操作会在这种电路图上失效:

广义串并联图

广义串并联图,GSPG,定义是不存在同胚于 K_4 子图的图。不加证明地,给出如下性质:

在 OI 中,我们最常用的是广义串并联图方法。

如果图是广义串并联图,则可以通过如上三种操作缩为单点。对于一般图,若 m \le n+k,则使用广义串并联图方法后可以得到 n\le 2k, m \le 3k 的图。

实现时,我们用 std::map 维护邻接矩阵,用队列维护度数 \le 2 的点进行搜索。

使用广义串并联图方法的题,难点主要在于设计 DP 状态,并讨论三种操作时 DP 值转移的等效性。

P6790 [SNOI2020] 生成树

给出一张 n 个点 m 条边的无向连通图,保证 G 在删去某条边后是仙人掌。求 G 的生成树数目,对 998244353 取模。

:::::success[题解]

我们声称 G 是广义串并联图。

设计 DP 状态为 f_e 表示 e 边在生成树上的方案数,g_e 表示 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[题解]

结论 行列式在二维差分后不变。

对矩阵 A 做二维差分,一次操作变为 A_{l-1,l-1},A_{r,r} 加 1,A_{l-1,r}, A_{r,l-1} 减 1。

观察 Matrix-Tree 定理的形式,发现度数矩阵减邻接矩阵的系数正好对上,将问题转化为连边 l-1 \leftrightarrow r 的生成树数目。

建图以后,使用和上一题相同的广义串并联图方法,将问题规约到 n \le 600,m \le 900 的子图上。

考虑使用 Matrix-Tree 定理求子图生成树数目。我们要求的是 \sum \limits_{T} \left(\prod\limits_{e \in T} f_e \right)\left(\prod\limits_{e \notin T} g_e \right),将边权赋为 \dfrac{f_e}{g_e} 求出 \sum \limits_{T} \prod\limits_{e \in T} \dfrac{f_e}{g_e} 并将答案乘上 \prod g_e 即可。

在 g_e \equiv 0 时上面的方法会爆掉,即 extra test #2 的 hack。为此,我们需要将 g_e \equiv 0 的必选边缩起来再进行上面的算法。

:::::

:::::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);
}

:::::