[TJOI2012]桥

xcxcli · 2019-10-04 13:48:46 · 题解

吐槽：一道曾经混在绿题里的紫题。

在正文的前面，先解释一下一些内容的定义。

从1\to n上的每个点u出发，开始bfs，向没有被搜过、id_v=0且u在1\to v上的点v搜索，并将其L_v设为id_u。如下图。

从n\to 1上的每个点u出发，开始bfs，向没有被搜过、id_v=0且u在n\to v上的点v搜索，并将其R_v设为id_u。如下图。

step2 求出res_i

容易发现，若要使1\to n的长度变大，一定要删除1\to n上的边。

考虑每条不在1\to n上的边u\to v，若删除st_{L_u}\to st_{R_v}中的一条边，则1\to n有可能经过u\to v，此时1\to n的长度为d1_u+w_{u,v}+dn_v。

而res_i就是所有满足st_{L_u}\le i\le st_{R_v}的边1\to n的长度的最小值。

所以我们只要枚举每一条边，区间修改[st_{L_u},st_{R_v}]的最小值，最终叶子结点的值就是res。可以用线段树维护。

更多细节详见代码。

#include<stdio.h>
#include<queue>
using namespace std;
int rd(){
    int k=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k;
}
const int N=100001;
int Min(int x,int y){return x<y?x:y;}
struct E{int v,w,nxt;}e[N<<2];
struct P{int p,w;};
bool operator<(P a,P b){return a.w>b.w;}
int n,m,h[N],cnt,u,v,w,d1[N],dn[N],id[N],st[N],T,L[N],R[N],t[N<<2],res[N];
priority_queue<P>q;queue<int>Q;bool I[N<<2];
void add(int u,int v,int w){e[++cnt]=(E){v,w,h[u]},h[u]=cnt;}
void Dijkstra(int x,int*d){
    for(int i=1;i<=n;++i)d[i]=2e9;
    d[x]=0,q.push((P){x,0});
    while(!q.empty()){
        u=q.top().p,w=q.top().w,q.pop();
        if(w>d[u])continue;
        for(int i=h[u];i;i=e[i].nxt){
            v=e[i].v;
            if(d[v]>e[i].w+w)d[v]=e[i].w+w,q.push((P){v,d[v]});
        }
    }
}//Dijkstra求d1,dn
void bfs(int x,int*d,int*f){
    Q.push(st[x]),f[st[x]]=x;
    while(!Q.empty()){
        u=Q.front(),Q.pop();
        for(int i=h[u];i;i=e[i].nxt){
            v=e[i].v;
            if(!id[v]&&!f[v]&&d[u]+e[i].w==d[v])f[v]=x,Q.push(v);
            //若不在最短路上、没有被访问过、且u在1->v上，就搜索v
        }
    }
}//bfs求L,R
#define p ((l+r)>>1)
#define ls (x<<1)
#define rs (x<<1|1)
void Make(int x,int l,int r){
    t[x]=2e9;
    if(l==r)return;
    Make(ls,l,p),Make(rs,p+1,r);
}
void Update(int x,int l,int r,int L,int R,int w){
    if(L<=l&&r<=R){t[x]=Min(t[x],w);return;}
    if(L<=p)Update(ls,l,p,L,R,w);
    if(p<R)Update(rs,p+1,r,L,R,w);
}
void Down(int x,int l,int r){
    if(l==r){res[l]=t[x];return;}
    t[ls]=Min(t[ls],t[x]),t[rs]=Min(t[rs],t[x]),Down(ls,l,p),Down(rs,p+1,r);
}
int main(){
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    n=rd(),m=rd();
    for(int i=1;i<=m;++i)u=rd(),v=rd(),w=rd(),add(u,v,w),add(v,u,w);
    Dijkstra(1,d1),Dijkstra(n,dn),u=1;
    while(u<n){
        st[++T]=u,id[u]=T;
        for(int i=h[u];i;i=e[i].nxt){
            v=e[i].v;
            if(dn[v]+e[i].w==dn[u]){I[i]=1,u=v;break;}//要标记边是否在最短路上
        }
    }
    st[++T]=n,id[n]=T;//求st,id
    for(int i=1;i<=T;++i)bfs(i,d1,L),bfs(i,dn,R);
    --T,Make(1,1,T);
    //有T个点，就有T-1条边，所以T要减1
    //建线段树时要将权值初始化为inf
    for(u=1;u<=n;++u)
        for(int i=h[u];i;i=e[i].nxt){
            v=e[i].v;
            if(!I[i]&&L[u]<R[v])Update(1,1,T,L[u],R[v]-1,d1[u]+e[i].w+dn[v]);
            //若边不在最短路上就进行区间修改。
        }
    Down(1,1,T),u=0,v=0;
    for(int i=1;i<=T;++i){
        if(u<res[i])u=res[i],v=1;
        else if(u==res[i])++v;
    }//统计最大值和方案数
    if(u==d1[n])v=m;//!!!
    //若删除一条边后1->n不变，那么删除每一条边效果相同，方案数为m
    printf("%d %d\n",u,v);
    return 0;
}