Election Campaign

问题概要

给你一个有 \(N\) 个点和 \(M\) 条边的简单无向图，点编号 \(1\) 到 \(N\)。边有两种类型，用字母 A 和 Y 表示。

你要从点 \(1\) 走到点 \(N\)，希望经过的两类边的数量之差的绝对值尽可能小。你可以多次经过一条边，每次经过都算次数。

求从点 \(1\) 走到点 \(N\)，经过的两类边的数量之差的最小最绝对值。若无法从点 \(1\) 走到点 \(N\)，输出 \(-1\)。

\(2 \le N \le 3\times 10^5\)
\(0 \le M \le 3 \times 10^5\)

换个说法

不妨把 A 类边视作具有边权 \(1\)，Y 类边视作具有边权 \(-1\)。我们求从点 \(1\) 走到点 \(N\) 经过的边的权值之和的最小绝对值。

思路

下列两个情况是简单的

点 \(1\) 和点 \(N\) 不连通。
点 \(1\) 和点 \(N\) 连通，但它们所在的连通块里只有一种边。

以下假设点 \(1\) 和点 \(N\) 连通，且它们所在的连通块里两种边都有。

考虑一个从点 \(1\) 到点 \(N\)，既经过正边也经过负边的走法。设它经过 \(L\) 条边，把经过的边依次记作 \(e_1, \dots, e_L\)，把这些边的权值之和记作 \(S\)。把经过的点依次记作 \(v_0, v_1, \dots, v_L\)，有 \(v_0 = 1\) 和 \(v_L = N\)。对于这个走法，我们注意到

如果 \(S\) 是非零偶数，那我们总可以通过在 \(e_1, \dots, e_L\) 中的某一条边上来回走，把 \(S\) 调整为 \(0\)。比如说 \(S = 4\)，我们在一条负边上走两个来回，\(S\) 就变成 \(0\)。同理，如果 \(S\) 是奇数，我们总可以把 \(S\) 调整为 \(1\)。

更进一步，我们注意到

如果经过的点 \(v_0, \dots, v_L\) 中有一个点在奇环上，我们总可以把 \(S\) 调整为偶数。这是因为奇环的边权和是奇数，每在奇环上绕一圈，\(S\) 的奇偶性就改变。

于是我们得到

答案要么是 \(0\)，要么是 \(1\)。
如果点 \(1\)（和点 \(N\)）所在的连通块里有奇环，答案是 \(0\)。
如果点 \(1\) 所在的连通块里没有奇环，那么这个连通块是个二分图，此时从 \(1\) 到 \(N\) 的任何走法，走过的边数的奇偶性是固定的。答案是 \(0\) 当且仅当点 \(1\) 和点 \(N\) 在同一侧。

程序实现

点击展开代码

/**
 *    author:  zjs
 *    created: 12.10.2026 06:43:42
**/
#include <bits/stdc++.h>
#include <cassert> // <bits/stdc++.h> does not include cassert since GCC 16.
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    struct Edge {
        int from, to;
        char type;
    };
    vector<vector<int>> g(n + 1);
    vector<Edge> e(m);
    for (int i = 0; i < m; i++) {
        int u, v;
        char c;
        cin >> u >> v >> c;
        e[i] = {u, v, c};
        g[u].push_back(i);
        g[v].push_back(i);
    }
    // bfs
    bool has_a = false;
    bool has_y = false;
    vector<int> color(n + 1);
    int dist_n;
    struct S {
        int u, color, dist;
    };
    queue<S> q;
    q.push({1, 1, 0});
    bool bipart = true;
    while (!q.empty()) {
        auto [u, c, d] = q.front();
        q.pop();
        if (color[u]) {
            if (color[u] != c)
                bipart = false;
            continue;
        }
        color[u] = c;
        if (u == n) dist_n = d;
        for (int i : g[u]) {
            if (e[i].type == 'A')
                has_a = true;
            else
                has_y = true;
            int v = e[i].from ^ e[i].to ^ u;
            q.push({v, -c, d + 1});
        }
    }
    if (!color[n])
        cout << -1 << '\n';
    else if (!has_a || !has_y) {
        cout << dist_n << '\n';
    } else if (bipart) {
        cout << (color[1] != color[n]) << '\n';
    } else  {
        cout << 0 << '\n';
    }
}