题解：P2685 [TJOI2012] 桥

【题解】P2685 [TJOI2012]桥

题意简述

给定一无向图，断掉其中一条边后，使得从点

1

到点

n

的最短路最长。求此最短路长度与此图中满足此条件的边数。

题目解法

这里提供一种使用割边的解法。

首先，我们求出在要求经过某一条边的的从点

1

到点

n

的路径中最短的路径长度。对于边

i

此值记值为

mindis_i

。

我们从小到大枚举所有

mindis_i

值，记当前所枚举的值为

now

用所有

mindis_i \le now

的边建图。如果在此图中点

1

与点

n

属于同一个边双联通分量，当条件首次成立时此图中切断任意一条边后的最短路长度最大值为

now

，满足此条件的边数为上一次所建图中点

1

到点

n

的最短路上的割边数。

具体算法

为了求出

mindis_i

这里以点

1

与点

n

为起点，分别跑一次单源最短路。对于边

(u,v)

而言，显然的，经过其的从点

1

到点

n

的路径中长度最短的路径长度是点

1

到点

u

的最短路长度，点

v

到点

n

的最短路长度与边

(u,v)

的长度之和。因为这是一个无向图，所以我们需要讨论边

(u,v)

的方向，并取其在两个方向上的最小值。

为了求出点

1

与点

n

是否属于同一个边双联通分量，我们可以使用 tarjan 算法求出图中的割边，并在删去割边的图中跑一遍 DFS 验证点

1

与点

n

是否连通，如连通，则说明点

1

与点

n

属于同一个边双联通分量。

关于此解法正确的说明

对于其中边

mindis_i \le now

的图中显然有总长度小于等于

now

的从点

1

到点

n

的路径存在。当断掉任意一条边

a

时

若 $mindis_a=now$ 此图相当于上一次枚举所建图，此图中显然有总长度小于 $now$ 的从点 $1$ 到点 $n$ 的路径存在。
若 $mindis_a<now$ 由于此图点 $1$ 与点 $n$ 是否属于同一个边双联通分量，所以点 $1$ 到点 $n$ 间显然存在一条不经过断边的路径，并且此路径中存在一条边其经过此边的的从点 $1$ 到点 $n$ 的路径中最短的路径中不包含断边，因为如果所有如此路径其包括断边，断边将是此图的一条割边，并且断掉后使点 $1$ 与点 $n$ 在此图上不连通，与前文的条件相斥。

综上，当前文的判断条件成立时，图中将有两条互不相交的点

1

到点

n

的路径，且这两条路径的长度均小于等于

now

，所以无论断掉任意一条边，从点

1

到点

n

的最短路长度将会小于等于

now

。

当对于上一次枚举所建的图，当断掉其中最短路上的割边时，点

1

到点

n

间将没有长度小于

now

的路径连通，即最短路上的割边数将是方案数。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=4e5+10;
struct edge{
    int s,t;
    long long c,mdis;
    int iid;
} e[MAXN];//边集
long long dis1[MAXN];
long long dis2[MAXN];
bool vis[MAXN];
vector<int> t[MAXN];
set<long long> dif;
vector<int> nt[MAXN];
vector<int> ft[MAXN];
bool isbrg[MAXN];
int dfn[MAXN];
int low[MAXN];
int n,m;
int id;
bool rch[MAXN];
edge prv[MAXN];
int ans=0;
void spfa(int s,long long dis[]){
    memset(vis,0,sizeof(vis));
    priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > q;
    dis[s]=0;
    q.push(make_pair(dis[s],s));
    vis[s]=true;
    while(!q.empty()){
        pair<long long,int> u=q.top();
        q.pop();
        vis[u.second]=false;
        for(int i:t[u.second]){
            if(dis[u.second]+e[i].c<dis[e[i].t]){
                dis[e[i].t]=dis[u.second]+e[i].c;
                prv[e[i].t]=e[i];
                if(!vis[e[i].t]){
                    q.push(make_pair(dis[e[i].t],e[i].t));
                    vis[e[i].t]=true;
                }
            }
        }
    }

}
bool CMP(const edge &a,const edge &b){
    if(a.mdis==b.mdis&&a.s==b.s&&a.t==b.t) return a.c<b.c;
    else if(a.mdis==b.mdis&&a.s==b.s) return a.t<b.t;
    else if(a.mdis==b.mdis) return a.s<b.s;
    else return a.mdis<b.mdis;
}
map<edge,int,std::function<bool(const edge&, const edge&)> > mpt(CMP);
set<edge,std::function<bool(const edge&, const edge&)> > sinp(CMP);
void tarjan(int p,int lst){
    dfn[p]=low[p]=++id;
    for(auto i:nt[p]){
        if(!dfn[e[i].t]){
            tarjan(e[i].t,i);
            if(dfn[p]<low[e[i].t]){
                isbrg[i]=isbrg[e[i].iid]=true;
            }
            low[p]=min(low[p],low[e[i].t]);
        }
        else if(i!=e[lst].iid){
            low[p]=min(low[p],dfn[e[i].t]);
        }
    }
}
bool DFS(int p){
    if(p==n) return true;
    rch[p]=true;
    for(auto i:nt[p]){
        if(!rch[e[i].t]&&!isbrg[i]&&DFS(e[i].t)){
            return true;
        }
    }
    return false;
}
signed main(){

    cin>>n>>m;
    if(n==1){
        cout<<0<<" "<<m<<endl;
        return 0;
    }
    for(int i=1;i<=2*m;i+=2){
        cin>>e[i].s>>e[i].t>>e[i].c;
        e[i+1]=e[i];
        swap(e[i+1].s,e[i+1].t);
        t[e[i].s].push_back(i);
        t[e[i].t].push_back(i+1);
    }
    memset(dis1,0x3f,sizeof(dis1));
    memset(dis2,0x3f,sizeof(dis2));
    spfa(1,dis1);
    edge nxt=prv[n];
    for(;nxt.s!=1;nxt=prv[nxt.s])
        sinp.insert(nxt);
    sinp.insert(nxt);
    spfa(n,dis2);
    nxt=prv[1];
    for(;nxt.s!=n;nxt=prv[nxt.s])
        sinp.insert(nxt);
    sinp.insert(nxt);
    for(int i=1;i<=2*m;i++){
        e[i].mdis=min(dis1[e[i].s]+dis2[e[i].t],dis1[e[i].t]+dis2[e[i].s])+e[i].c;
        dif.insert(e[i].mdis);
    }
    sort(e+1,e+1+2*m,CMP);
    for(int i=1;i<=2*m;i++){
        edge tmp=e[i];
        swap(tmp.s,tmp.t);
        if(mpt.count(tmp)){
            e[i].iid=mpt[tmp];
            e[mpt[tmp]].iid=i;
        }
        else{
            mpt[e[i]]=i;
        }
    }
    int nw=1,lstl=0;
    ans=m;
    for(long long i:dif){
        lstl=ans;
        ans=0;
        for(;nw<=2*m&&e[nw].mdis<=i;nw++){
            nt[e[nw].s].push_back(nw);
        }
        id=0;
        memset(isbrg,0,sizeof(isbrg));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(rch,0,sizeof(rch));
        for(int j=1;j<=n;j++){
            if(!dfn[j]) tarjan(j,-1);
        }
        for(int j=1;j<=2*m;j++){
            edge tmp=e[j];
            tmp.iid=0;
            tmp.mdis=0;
            if(isbrg[j]&&sinp.count(tmp)) ans++;
        }
        ans/=2;
        if(DFS(1)){
            cout<<i<<" "<<lstl<<endl;
            break;
        }
    }

    return 0;
}

题解：P2685 [TJOI2012] 桥

文章操作