bzoj2725:[Violet 6]故乡的梦 bzoj4400:tjoi2012 桥(最短路+并查集)

Author Avatar
Sakits 3月 08, 2018

题解

  剧毒,打错一个字符调了一天…
  这两题好像还没有并查集的题解?那个线段树不是显然可以用并查集代替吗QAQ
  首先肯定要删掉SSTT最短路径上的边才对答案有影响,所以我们先随便求出一条钦定的SSTT的最短路径,设这条最短路径为LL
  那么可以考虑枚举不在LL上的边(x,y)(x,y),算出强制走这条边的最短距离。这条最短路一定是从LL上的一点离开,经过(x,y)(x,y),再回到LL上某一点。设它从gos[x]gos[x]离开LL,从got[y]got[y]回到LL,那么断掉LLgos[x]gos[x]got[y]got[y]之间的边就有可能走经过(x,y)(x,y)的最短路。
  所以只需要对于每条不在SSTT最短路径上的边,算出强制经过这条边的最短路,然后按最短路长度升序排序,从小到大对LL上的边赋值为此长度,赋值过的边就没有必要再赋值了,所以可以用并查集压缩掉赋值过的那些边,最后删掉LL上某条边之后SSTT的最短路会变多长的答案就存在那条边上了。
  怎么求gos[]gos[]got[]got[]?要注意的一点是,对于(x,y)(x,y),我们要找SS的最短路径树上深度最浅的gos[x]gos[x]和最深的got[y]got[y],因为这样才能使覆盖的范围最大。那么分别在最短路径上从上到下和从下到上对每个点dfs,能以最短路径到达的点记录一下从哪个点出发的即可。

bzoj2725代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=500010;
const ll inf=1e18;
struct poi{int x; ll dis;};
struct tjm{int x, y; ll dis;}a[maxn];
struct edge{int too, dis, pos, pre;}e[maxn<<1];
priority_queue<poi>q;
bool operator < (poi a, poi b){return a.dis>b.dis;}
int n, m, s, t, tot, cnt, tott;
int x[maxn], y[maxn], z[maxn], got[maxn], gos[maxn], last[maxn], fa[maxn], son[maxn];
int dep[maxn], pre[maxn], preedge[maxn], h[maxn], pos[maxn], way[maxn], fq[maxn];
ll ds[maxn], dt[maxn], ans[maxn];
bool v[maxn], vis[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
bool operator < (tjm a, tjm b){return a.dis<b.dis;}
inline void add(int x, int y, int z, int pos){e[++tot]=(edge){y, z, pos, last[x]}; last[x]=tot;}
inline void dij(int s, ll dist[])
{
    for(int i=1;i<=n;i++) dist[i]=inf; dist[s]=0;
    q.push((poi){s, 0});
    while(!q.empty())
    {
        poi now=q.top(); q.pop();
        if(dist[now.x]!=now.dis) continue;
        for(int i=last[now.x], too;i;i=e[i].pre)
        if(dist[too=e[i].too]>dist[now.x]+e[i].dis)
        {
            dist[too]=dist[now.x]+e[i].dis;
            pre[too]=now.x; preedge[too]=e[i].pos;
            q.push((poi){too, dist[too]});
        }   
    }
}
int gf(int x){return fa[x]==x?fa[x]:fa[x]=gf(fa[x]);}
void bfs(int x, int go[], ll dist[])
{
    go[x]=x; int front=0, rear=1; h[1]=x;
    while(front!=rear)
    {
        int now=h[++front];
        if(front==maxn-1) front=-1;
        for(int i=last[now], too;i;i=e[i].pre)
        if(!go[too=e[i].too] && !pos[too] && dist[too]==dist[now]+e[i].dis)
        h[++rear]=too, go[too]=x;
    }
}
int main()
{
    read(n); read(m);
    for(int i=1;i<=m;i++) 
    read(x[i]), read(y[i]), read(z[i]), add(x[i], y[i], z[i], i), add(y[i], x[i], z[i], i);
    read(s); read(t);  int Q; read(Q);
    dij(t, dt); dij(s, ds); pre[s]=preedge[s]=0; int nowx=t;    
    if(ds[t]==inf)
    {
        while(Q--) puts("Infinity");
        return 0;
    }
    while(nowx) way[++cnt]=nowx, pos[nowx]=cnt, nowx=pre[nowx];
    for(int i=1;i<=cnt;i++) bfs(way[i], got, dt);
    for(int i=cnt;i;i--) bfs(way[i], gos, ds);
    for(int i=1;i<=n;i++) ans[i]=inf;
    for(int i=1;i<=n;i++) vis[preedge[i]]=1;
    for(int i=1;i<=m;i++)
    if(!vis[i])
    {
        a[++tott].x=gos[x[i]]; a[tott].y=got[y[i]]; a[tott].dis=ds[x[i]]+z[i]+dt[y[i]];
        a[++tott].x=gos[y[i]]; a[tott].y=got[x[i]]; a[tott].dis=ds[y[i]]+z[i]+dt[x[i]];
    }
    for(int i=1;i<=cnt;i++) fq[way[i]]=way[i+1], son[way[i+1]]=way[i], dep[way[i]]=cnt-i+1, fa[way[i]]=way[i];
    sort(a+1, a+1+tott);
    for(int i=1;i<=tott;i++)
    {
        int x=a[i].x, y=a[i].y;
        if(dep[x]<dep[y]) swap(x, y); y=son[y];
        x=gf(a[i].x), y=gf(a[i].y);
        while(x!=y)
        {       
            if(dep[x]<dep[y]) swap(x, y);
            if(!v[x]) ans[x]=min(ans[x], a[i].dis), v[x]=1;
            x=fa[x]=gf(fq[x]); 
        }   
    }
    while(Q--)
    {
        int x, y;
        read(x); read(y);
        if(x==y) {printf("%lld\n", ds[t]); continue;}
        if(pos[x]<pos[y]) swap(x, y);
        if(!pos[y] || abs(pos[x]-pos[y])>1) printf("%lld\n", ds[t]);
        else
        {
            if(ans[y]>=inf) puts("Infinity");
            else printf("%lld\n", ans[y]);
        }
    }
}

bzoj4400代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=200010;
const ll inf=1e18;
struct poi{int x; ll dis;};
struct tjm{int x, y; ll dis;}a[maxn];
struct edge{int too, dis, pos, pre;}e[maxn<<1];
priority_queue<poi>q;
bool operator < (poi a, poi b){return a.dis>b.dis;}
int n, m, tot, cnt, tott;
int x[maxn], y[maxn], z[maxn], got[maxn], gos[maxn], last[maxn], fa[maxn], son[maxn];
int dep[maxn], pre[maxn], preedge[maxn], h[maxn], pos[maxn], way[maxn], fq[maxn];
ll ds[maxn], dt[maxn], ans[maxn];
bool v[maxn], vis[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
bool operator < (tjm a, tjm b){return a.dis<b.dis;}
inline void add(int x, int y, int z, int pos){e[++tot]=(edge){y, z, pos, last[x]}; last[x]=tot;}
inline void dij(int s, ll dist[])
{
    for(int i=1;i<=n;i++) dist[i]=inf; dist[s]=0;
    q.push((poi){s, 0});
    while(!q.empty())
    {
        poi now=q.top(); q.pop();
        if(dist[now.x]!=now.dis) continue;
        for(int i=last[now.x], too;i;i=e[i].pre)
        if(dist[too=e[i].too]>dist[now.x]+e[i].dis)
        {
            dist[too]=dist[now.x]+e[i].dis;
            pre[too]=now.x; preedge[too]=e[i].pos;
            q.push((poi){too, dist[too]});
        }
    }
}
int gf(int x){return fa[x]==x?fa[x]:fa[x]=gf(fa[x]);}
void bfs(int x, int go[], ll dist[])
{
    go[x]=x; int front=0, rear=1; h[1]=x;
    while(front!=rear)
    {
        int now=h[++front];
        if(front==maxn-1) front=-1;
        for(int i=last[now], too;i;i=e[i].pre)
        if(!go[too=e[i].too] && !pos[too] && dist[too]==dist[now]+e[i].dis)
        h[++rear]=too, go[too]=x;
    }
}
int main()
{
    read(n); read(m);
    for(int i=1;i<=m;i++) 
    read(x[i]), read(y[i]), read(z[i]), add(x[i], y[i], z[i], i), add(y[i], x[i], z[i], i);
    dij(n, dt); dij(1, ds); pre[1]=preedge[1]=0; int nowx=n;
    while(nowx) pos[nowx]=1, way[++cnt]=nowx, nowx=pre[nowx];
    for(int i=1;i<=cnt;i++) bfs(way[i], got, dt);
    for(int i=cnt;i;i--) bfs(way[i], gos, ds);
    for(int i=1;i<=n;i++) ans[i]=inf;
    for(int i=1;i<=n;i++) vis[preedge[i]]=1;
    for(int i=1;i<=m;i++)
    if(!vis[i])
    {
        a[++tott].x=gos[x[i]]; a[tott].y=got[y[i]]; a[tott].dis=ds[x[i]]+z[i]+dt[y[i]];
        a[++tott].x=gos[y[i]]; a[tott].y=got[x[i]]; a[tott].dis=ds[y[i]]+z[i]+dt[x[i]];
    }
    for(int i=1;i<=cnt;i++) fq[way[i]]=way[i+1], son[way[i+1]]=way[i], dep[way[i]]=cnt-i+1, fa[way[i]]=way[i];
    sort(a+1, a+1+tott); 
    for(int i=1;i<=tott;i++)
    {
        int x=a[i].x, y=a[i].y;
        if(dep[x]<dep[y]) swap(x, y); y=son[y];
        x=gf(a[i].x), y=gf(a[i].y);
        while(x!=y)
        {       
            if(dep[x]<dep[y]) swap(x, y);
            if(!v[x]) ans[x]=min(ans[x], a[i].dis), v[x]=1;
            x=fa[x]=gf(fq[x]); 
        }   
    }
    ll ANS=0; int ANScnt=0;
    for(int i=1;i<cnt;i++)
    if(ans[way[i]]>ANS) ANS=ans[way[i]], ANScnt=1;
    else if(ans[way[i]]==ANS) ANScnt++;
    if(ANS==ds[n]) return printf("%lld %d\n", ANS, m), 0;
    printf("%lld %d\n", ANS, ANScnt);
}