二分真的太好用了你知道吗

listgv · 2026-10-22 09:50:52 · 题解

看到题目，发现要使最小值最大，考虑二分。

先以 1 和 n 为起点跑两遍最短路，得到每个点到这两点的距离，然后二分删边后的最短路长度，不妨设为 L，枚举原图每一条边，如果存在一条经过它的 1 到 n 的路径，长度 \le L，就将这个边加入新图。

对新图跑边双 tarjan，如果 1 和 n 不连通或者之间有割边就说明实际答案 d>L，否则 d\le L。

最后判一下，如果 d 等于最短路则方案数为 m，否则为 L=d-1 时 1 和 n 间的割边数量。

好处是不用写一堆特判，思维和代码难度双低，比线段树好想一万倍。

:::info[正确性] 下证新图 1,n 间不联通或有割边与 d>L 的充要关系。

首先如果不连通，充分性显然。

然后，如果有割边，说明 1,n 间长度 \le L 的路径都要经过这一个边，只要把这个边砍掉那就没有 \le L 的路径了，于是充分性得到。

必要性，考虑证明否命题，即 1,n 在同一边双内可导出 d\le L。此时取出 1,n 间的最短路，如果删边不在最短路上显然不优。

删边在最短路上，显然对于最短路上任意一条边都有不经过它的长度 \le L 的路径（不然它就是割边），所以删哪条边都有 d\le L。

证毕。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define llg long long
#define usg unsigned
#define ull unsigned long long
const int inf=1ll<<50;
vector<int>g[100005],f[100005];
int n,m,vis[100005];
struct node{
    int id,vl;
    bool operator <(const node &z)const{
        return vl<z.vl;
    }
    bool operator >(const node &z)const{
        return vl>z.vl;
    }
};
priority_queue<node,vector<node>,greater<node> >q;
void dijk(int st,int *dis){
    for(int i=1;i<=n;++i)dis[i]=inf,vis[i]=0;
    q.push(node{st,0});
    dis[st]=0;
    while(q.size()){
        node h=q.top();
        q.pop();
        if(vis[h.id])continue;
        vis[h.id]=1;
        for(int i=0;i<g[h.id].size();++i){
            int u=g[h.id][i],v=f[h.id][i];
            if(vis[u]||dis[u]<=h.vl+v)continue;
            dis[u]=h.vl+v;
            q.push(node{u,dis[u]});
        }
    }
}
int dis[2][100005];
vector<int>gg[100005];
int dft,dfn[100005],low[100005],scc,bl[100005];
stack<int>stk;
void dfs1(int x,int y){
    dfn[x]=low[x]=++dft;
    stk.push(x);
    for(int i=0;i<gg[x].size();++i){
        int u=gg[x][i];
        if(u==y){
            y=0;
            continue;
        }
        if(!dfn[u]){
            dfs1(u,x);
            low[x]=min(low[x],low[u]);
        }else if(!bl[u])low[x]=min(low[x],dfn[u]);
    }
    if(dfn[x]==low[x]){
        ++scc;
        while(1){
            int u=stk.top();
            stk.pop();
            bl[u]=scc;
            if(u==x)break;
        }
    }
}
int dds[100005];
void dfs2(int x,int y){
    dds[x]=y;
    for(int i=0;i<gg[x].size();++i){
        int u=gg[x][i];
        if(~dds[u])continue;
        if(bl[u]==bl[x])dfs2(u,y);
        else dfs2(u,y+1);
    }
}
int check(int x){
    for(int i=1;i<=n;++i)gg[i].clear(),dds[i]=-1,dfn[i]=0,bl[i]=0;
    dft=0;
    scc=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<g[i].size();++j){
            int u=g[i][j],v=f[i][j];
            if(i<u){
                if(dis[0][i]+v+dis[1][u]<=x||dis[0][u]+v+dis[1][i]<=x){
                    gg[i].push_back(u);
                    gg[u].push_back(i);
                }
            }
        }
    }
    for(int i=1;i<=n;++i)if(!dfn[i])dfs1(i,0);
    dfs2(1,0);
    return dds[n]==-1?inf:dds[n];
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back(y);
        g[y].push_back(x);
        f[x].push_back(z);
        f[y].push_back(z);
    }
    dijk(1,dis[0]);
    dijk(n,dis[1]);
    int l=0,r=1<<30;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))l=mid+1;
        else r=mid;
    }
    cout<<l<<" ";
    if(l==dis[0][n])cout<<m;
    else cout<<check(l-1);
    return 0;
}

:::