P8426 [JOI Open 2022] 放学路（School Road）

· · 题解

题目链接

根据部分分大力得到正解，一步步来。

首先对于 m\leq 40 可以搜索出所有路径，n\leq 18 直接状压，那么目光聚集于 m-n\leq 13。

不难条件反射出广义串并联图方法（广告：广义串并联图方法学习笔记），缩合后得到 m\leq 3\times 13 同样可以搜索做，当然这一方法的作用不止于此。

首先先描述一下具体的缩合方法：

自行想象一下 no 的情况，大概就是所有 1\to n 的简单路径们都缩到了 (1,n) 这唯一一条边上，且边权不为 -1。

于是大胆断言答案为 no 当且仅当：缩合后 s 的唯一出边是 (s,t,w)，且 w\neq -1。

当然这个猜测随便 hack，比如 Froggy 在 LOJ 讨论 里提到的 hack 长这样：

虽然这个 hack 看上去有些取巧，但是至少是个 hack，而且变相的更加使我们相信这个不靠谱的猜想有一定正确性。

再看一眼部分分，发现有：对于任意三座不同的城市 a, b, c，均存在一条从城市 a 到城市 c 且不经过城市 b 的路径 这个 sub。

翻译成人话就是整个图形成一个点双，同时不难发现上述 hack 的思路就是存在不同时包含 1 和 n 的点双。

那么难道说如果整张图是一个点双上述猜想就正确吗，实际上是这样的，证明如下：

此处证明参考官方题解并结合自己的一点思考，可以看作是本题最核心部分之一。

首先整理一下已知条件：整个图是点双联通的且所有点的度数 \geq 3。同时有点数 n\geq 4，否则无法满足度数均 \geq 3 的限制。

考虑将所有边定向，根据从 1 到它们的最短路，与最短路扩展方向同向定向。

如果此时就有 (u,v,w) 使得 \text{dis}(1,u)+w+\text{dis}(v,n)\neq \text{dis}(1,n) 的话那肯定是没救了。

否则定向后，称入度 > 出度的点为红色点，否则称为蓝色点。

然后考虑 1\to n 的经过节点个数最多的简单路径，1\to a_1\to a_2\to \cdots\to a_p\to n。

首先得到 a_1 入度一定是 1，a_p 的出度一定是 1，否则一定能找到经过点数更多的路径。

同时由于任意点度数 \geq 3，所以 a_1 一定是蓝色的，a_p 一定是红色的，换言之，路径一定经历了蓝红替换的过程。

考虑找到这样一条边，使得 a_i=u,a_{i+1}=v，且 u 为蓝色，v 为红色。

根据定义，一定存在 u\to x(x\neq v) 以及 y\to v(y\neq u)，此时考虑路径 1\to y\to v\to u\to x\to n。

除了 v\to u 之外，所有边任然需要根据定向移动。

如果它不是简单路径，不难发现只有可能是 x\to n 与 1\to y\to v 这段路径上有重合，不妨设第一个重合点为 x'。

那么将原路径替换为 1\to u\to x\to z\to y\to v\to n 是经过更多点的选择，不符合定义。

所以这条路径一定是简单的，且 > 最短路径的。证毕。

如此，所有非正解的部分分都有了解决方法。

当然更进一步也是容易的，因为如果从 1 出发进入一个以 1 为割点且不包含 n 的点双肯定是没有简单路径能到 n 的。

所以直接加一条 (1,n,\text{dis}(1,n)) 即等于它们之间最短路径的边，然后只考虑同时包含 1,n 的这个点双即可。

复杂度 O(m\log m)。

#include<bits/stdc++.h>
typedef long long ll;
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define per(i, a, b) for(int i = (a); i >= (b); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

#define eb emplace_back
typedef pair<int, ll> pii;
#define mp make_pair
#define fi first
#define se second

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

const int N = 1e5 + 10;
const ll inf = 1e16;
int n, m;

unordered_map<int, ll> g[N];

void add(int u, int v, ll w) {
    if(g[u].find(v) != g[u].end()) {
        if(g[u][v] != w) g[u][v] = g[v][u] = -1;
    }
    else g[u][v] = g[v][u] = w;
}

ll dis[N]; bool vis[N];
vector<pii> h[N];

ll getdis() {
    priority_queue<pair<ll, int> > q;
    rep(i, 1, n) dis[i] = inf;
    dis[1] = 0, q.push(mp(0, 1));
    while(! q.empty()) {
        int u = q.top().se; q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto e : h[u]) {
            int v = e.fi; ll w = e.se;
            if(dis[v] > dis[u] + w)
                dis[v] = dis[u] + w, q.push(mp(- dis[v], v));
        }
    }
    return dis[n];
}

int dfn[N], low[N], stk[N], top, tim, cnt;
vector<int> scc[N];

void dfs(int u) {
    dfn[u] = low[u] = ++ tim;
    stk[++ top] = u;
    for(auto e : h[u]) {
        int v = e.fi;
        if(! dfn[v]) {
            dfs(v), low[u] = min(low[u], low[v]);
            if(low[v] == dfn[u]) {
                int o = 0; cnt ++;
                do {o = stk[top --], scc[cnt].eb(o);} while(o != v);
                scc[cnt].eb(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

bool valid[N];

void build() {
    n = read(), m = read();
    rep(i, 1, m) {
        int u = read(), v = read(), w = read();
        h[u].eb(mp(v, w));
        h[v].eb(mp(u, w));
    }
    ll cur = getdis();
    h[1].eb(mp(n, cur));
    h[n].eb(mp(1, cur));
    dfs(1);
    rep(i, 1, n) vis[i] = false;
    int pos = 0;
    rep(i, 1, cnt) {
        for(int o : scc[i]) vis[o] = true;
        if(vis[1] && vis[n]) {pos = i; break;}
        for(int o : scc[i]) vis[o] = false;
    }
    assert(pos);
    for(int o : scc[pos]) valid[o] = true;
    rep(u, 1, n) if(valid[u])
    for(auto e : h[u]) if(valid[e.fi]) add(u, e.fi, e.se);
}

queue<int> q;
void push(int u) {if(u != 1 && u != n && (int) g[u].size() <= 2) q.push(u);}

int main() {
    build();
    rep(i, 1, n) push(i);
    while(! q.empty()) {
        int u = q.front(); q.pop();
        if(g[u].empty()) continue;
        for(auto o : g[u]) g[o.fi].erase(u);
        if((int) g[u].size() == 2) {
            auto cur = g[u].begin();
            int x = cur -> fi; ll a = cur -> se; cur ++;
            int y = cur -> fi; ll b = cur -> se;
            ll w = (a == -1 || b == -1) ? -1 : a + b;
            add(x, y, w);
        }
        for(auto o : g[u]) push(o.fi);
        g[u].clear();
    }
    if(g[1].find(n) != g[1].end() && g[1][n] != -1 && (int) g[1].size() == 1) puts("0"); else puts("1");
    return 0;
}