P8426 题解

· · 题解

P8426 题解

题目大意

给一张 n 个点 m 条边的带权无向连通图，问是否存在一条 1\to n 的简单路径长度与最短路长度不同。

数据范围：n\le 10^5,m\le 2\times 10^5。

思路分析

首先我们考虑简单一点的情况：不妨设整张图点双联通，感觉上这张图不能太复杂，否则肯定会找到解。

手模样例可以发现：假如这张图同胚于 K_4，即有四个点之间能找到六条边不交的路径将它们两两连接，那么这个图一定无解：

不妨设这四个点是 a,b,c,d，假设这张图依然无解，简单推理一下：

  • 由于 w(a\to b\to c)=w(a\to d\to b\to c)，因此 w(a,d)+w(d,b)=w(a,b)。
  • 由于 w(a\to d\to c)=w(a\to b\to d\to c)，因此 w(a,d)=w(a,b)+w(b,d)。

因此 w(b,d)=w(a,b)-w(a,d)=w(a,d)-w(a,b)=0，又因权值都是正整数，因此假设不成立，这样的图必然有解。

因此我们得到：同胚于 K_4 的点双联通图必定有解。

注意到不同胚于 K_4 的点就是广义串并联图，考虑广义串并联图方法简化这张图：

注意增广的过程中要保证 1,n 两个点不能入队，最后假如的图里只剩一条 1\to n 的边，且边权不为 -\infty 则合法，否则显然一定不合法。

然后考虑如何把图变成点双联通的，首先如果 1,n 点双联通，直接缩点，取出 1,n 所在的点双联通分量作为原图即可。

若 1,n 不点双联通，那么连接一条 1,n 之间的边，权值为他们之间的最短路长度，显然不影响答案判定，且能使得 1,n 点双联通。

时间复杂度 \mathcal O(m\log m)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
int n,m;
struct Edge { int v; ll w; };
vector <Edge> G[MAXN];
ll dis[MAXN];
bool vis[MAXN];
inline ll Dijk() {
    memset(dis,0x3f,sizeof(dis));
    priority_queue <array<ll,2>,vector<array<ll,2>>,greater<array<ll,2>>> Q;
    Q.push({dis[1]=0,1});
    while(Q.size()) {
        int u=Q.top()[1]; Q.pop();
        if(vis[u]) continue; vis[u]=true;
        for(auto e:G[u]) if(dis[e.v]>dis[u]+e.w) Q.push({dis[e.v]=dis[u]+e.w,e.v});
    }
    return dis[n];
}
vector <int> vdcc;
int dfn[MAXN],low[MAXN],dcnt,stk[MAXN],tp;
inline void tarjan(int u) {
    dfn[u]=low[u]=++dcnt,stk[++tp]=u;
    for(auto e:G[u]) {
        int v=e.v;
        if(!dfn[v]) {
            tarjan(v),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) {
                int k; vector <int> cur{u};
                do k=stk[tp--],cur.push_back(k); while(k!=v);
                sort(cur.begin(),cur.end());
                if(cur.front()==1&&cur.back()==n) vdcc=cur;
            }
        } else low[u]=min(low[u],dfn[v]);
    }
}
bool inq[MAXN];
map <int,ll> g[MAXN];
inline void link(int u,int v,ll w) {
    if(g[u].count(v)) {
        if(w!=g[u][v]) g[u][v]=g[v][u]=-1;
    } else g[u][v]=g[v][u]=w;
}
queue <int> Q;
inline void upd(int x) { if(x!=1&&x!=n&&g[x].size()<=2) Q.push(x); }
signed main() {
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,w;i<=m;++i) {
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    ll dist=Dijk();
    G[1].push_back({n,dist});
    G[n].push_back({1,dist});
    tarjan(1);
    for(int i:vdcc) inq[i]=true;
    for(int u:vdcc) for(auto e:G[u]) if(inq[e.v]) link(u,e.v,e.w);
    for(int i:vdcc) upd(i);
    while(Q.size()) {
        int u=Q.front(); Q.pop();
        for(auto e:g[u]) g[e.first].erase(u);
        if(g[u].size()==2) {
            int x=g[u].begin()->first,y=g[u].rbegin()->first;
            ll c=g[u].begin()->second,d=g[u].rbegin()->second;
            link(x,y,(~c&&~d)?c+d:-1);
        }
        for(auto e:g[u]) upd(e.first);
        g[u].clear();
    }
    if(g[1].count(n)&&~g[1][n]&&g[1].size()==1) puts("0");
    else puts("1");
    return 0;
}