【先祝贺一下@Jollwish神犇进入CMO国家集训队……合肥OI人总算出了个国家集训队员(虽然不是OI的)……

最近捉了两道猥琐题……都是有关图中删去某边后的最短路径的问题……核心思想几乎相同……但是,它们很明显是综合题,代码量太大了(与NOIP2012driveblockade有得一拼……),因此,从这之中可以得出综合题的一些应对方法。

1[Usaco2009 Jan]安全路经Travel
一个无向图,从源点s到每个点的最短路唯一,求对于每个点i,若将图中从si的最短路上的最后一条边删除,从si的最短路是多少。
由于最短路都唯一,所以s开始的SPT是一棵树……
对于非根结点i,将i的父边删除后,树分为两个部分,s所在的部分记为Si所在的部分(即子树i)记为T
可以发现,新的图中si的路径,必然是从s开始,先在S部分中走连续的一段,再经过一条边进入T部分,再在T部分中走连续的一段到i……
因为,一旦到了T,就不会再回到S了囧(否则可以直接从s沿着树边走到那里,不必从T绕了),又因为每个点都属于ST,所以必然只有一条边从ST……
s开始走连续的一段,必然是走树边的,设走到x,则长度就是根结点sx的路径长,设为D[x]……
然后,经过一条边(x, y)走到T中的结点y,由于iT的根,所以接下来必然是从y向上走到i,路径长是D[y]-D[i]……
也就是,从si新的最短路长就是min{D[x]+W(x, y)+D[y]}-D[i],其中(x, y)边满足:x不在子树i中,y在子树i中,(x, y)边不在SPT树上。
因此,只需要求出SPT树后,枚举所有不在树上的边<x, y>(每条无向边拆成两条有向边),它能影响的范围是[y..LCA(x, y))(注意LCA不能算),取最小值,用路径剖分解决即可……
写代码的时候的几个注意点:
1)(最坑爹的)最短路不能用SPFA,要用Dijk+HeapPQ无压力)!!!!!!!!!!!!!MS下一题也是如此……
2LCA(x, y)不能算,特别是当yx的祖先的时候,这条边<x. y>不能对任何结点的最小值产生影响,此时计算出的l>r,一定要特判,不能进入线段树操作!!线段树操作中l>r是会爆的!!
3)注意-1的情况……

代码(本沙茶在线段树那里很明显写傻了,大家知道囧……

#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<algorithm>
#include 
<queue>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 100010, MAXM = 200010, INF = ~0U >> 2;
struct edge0 {
    
int a, b, w, pre, next;
} E0[MAXM 
+ MAXM + MAXN];
struct edge1 {
    
int a, b, w;
    
bool operator< (edge1 e0) const {return w > e0.w;}
} E1[MAXM 
<< 1];
struct edge {
    
int a, b, pre, next;
    
bool Z;
} E[MAXN 
<< 1];
struct node {
    
int mr, lch, rch;
} T[MAXN 
<< 1];
int n, m0, m, dist[MAXN], Q[MAXN], pr[MAXN], SZ[MAXN], N, UP[MAXN], DEP[MAXN], tot[MAXN], root[MAXN];
int _V[MAXN], V_tmp[MAXN], l0, r0, v0;
bool vst[MAXN];
struct qnode {
    
int No, d0;
    
bool operator< (qnode q0) const {return d0 > q0.d0;}
};
priority_queue 
<qnode, vector<qnode> > Q0;
void init_d()
{
    re(i, n) E0[i].pre 
= E0[i].next = E[i].pre = E[i].next = i; m0 = m = n;
}
void add_edge0(int a, int b, int w)
{
    E0[m0].a 
= a; E0[m0].b = b; E0[m0].w = w; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
    E0[m0].a 
= b; E0[m0].b = a; E0[m0].w = w; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b)
{
    E[m].a 
= a; E[m].b = b; E[m].Z = 0; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
    
int _m, _a, _b, _w;
    scanf(
"%d%d"&n, &_m); init_d();
    re(i, _m) {
        scanf(
"%d%d%d"&_a, &_b, &_w);
        add_edge0(
--_a, --_b, _w);
    }
}
int mkt(int l, int r)
{
    
int N0 = ++N;
    
if (l < r) {
        T[N0].mr 
= 0int mid = l + r >> 1;
        T[N0].lch 
= mkt(l, mid); T[N0].rch = mkt(mid + 1, r);
    } 
else T[N0].mr = INF;
    
return N0;
}
void dm(int No)
{
    
int _, __;
    
if (_ = T[No].mr) {
        T[No].mr 
= 0;
        
if (__ = T[No].lch) T[__].mr = _;
        
if (__ = T[No].rch) T[__].mr = _;
    }
}
void opr0(int l, int r, int No)
{
    
if (l >= l0 && r <= r0) T[No].mr = v0; else {
        dm(No);
        
int mid = l + r >> 1, lch = T[No].lch, rch = T[No].rch;
        
if (mid >= l0) opr0(l, mid, lch);
        
if (mid < r0) opr0(mid + 1, r, rch);
    }
}
void visit(int l, int r, int No)
{
    
if (l == r) V_tmp[l] = T[No].mr; else {
        dm(No);
        
int mid = l + r >> 1;
        visit(l, mid, T[No].lch);
        visit(mid 
+ 1, r, T[No].rch);
    }
}
void prepare()
{
    qnode q0; q0.No 
= q0.d0 = 0; Q0.push(q0); re2(i, 1, n) dist[i] = INF;
    
int x, y, d0;
    
while (!Q0.empty()) {
        x 
= Q0.top().No; Q0.pop();
        
if (!vst[x]) {
            vst[x] 
= 1;
            
for (int p=E0[x].next; p != x; p=E0[p].next) {
                y 
= E0[p].b; d0 = dist[x] + E0[p].w;
                
if (d0 < dist[y]) {dist[y] = d0; q0.No = y; q0.d0 = d0; Q0.push(q0);}
            }
        }
    }
    re2(i, n, m0) {
        x 
= E0[i].a; y = E0[i].b;
        
if (dist[x] + E0[i].w == dist[y]) {pr[y] = m; add_edge(x, y);}
    }
    Q[
0= DEP[0= 0;
    
for (int front=0, rear=0; front<=rear; front++) {
        x 
= Q[front];
        
for (int p=E[x].next; p != x; p=E[p].next) {y = E[p].b; Q[++rear] = y; DEP[y] = DEP[x] + 1;}
    }
    
int z, maxsz;
    rre(i, n) {
        x 
= Q[i]; SZ[x] = 1; maxsz = -INF;
        
for (int p=E[x].next; p != x; p=E[p].next) {
            y 
= E[p].b; SZ[x] += SZ[y]; if (SZ[y] > maxsz) {maxsz = SZ[y]; z = y;}
        }
        
if (maxsz > 0) E[pr[z]].Z = 1;
    }
    re(i, n) vst[i] 
= 0;
    rre2(i, n, 
1) {
        x 
= Q[i];
        
if (E[pr[x]].Z && !vst[x]) {
            
for (y=x; y && E[pr[y]].Z; y=E[pr[y]].a) vst[y] = 1;
            UP[y] 
= y; tot[y] = DEP[x] - DEP[y] + 1; root[y] = mkt(0, tot[y] - 1);
            
for (int j=x; j!=y; j=E[pr[j]].a) {UP[j] = y; tot[j] = tot[y]; root[j] = root[y];}
        }
    }
    re(i, n) {_V[i] 
= INF; if (SZ[i] == 1 && !E[pr[i]].Z) UP[i] = i;}
}
int LCA(int u, int v)
{
    
while (UP[u] != UP[v]) if (DEP[UP[u]] >= DEP[UP[v]]) u = E[pr[UP[u]]].a; else v = E[pr[UP[v]]].a;
    
return DEP[u] <= DEP[v] ? u : v;
}
void solve()
{
    
int x, y, z, _, w0, m1 = 0;
    re2(i, n, m0) {
        x 
= E0[i].a; y = E0[i].b; w0 = E0[i].w;
        
if (dist[x] + w0 != dist[y] && dist[y] + w0 != dist[x]) {
            E1[m1].a 
= x; E1[m1].b = y; E1[m1++].w = dist[x] + dist[y] + w0;
        }
    }
    sort(E1, E1 
+ m1);
    re(i, m1) {
        x 
= E1[i].a; y = E1[i].b; z = LCA(x, y);
        
if (y == z) continueelse v0 = E1[i].w;
        
if (SZ[y] == 1 && !E[pr[y]].Z) {_V[y] = v0; y = E[pr[y]].a;}
        
while (y != z) {
            _ 
= UP[y];
            
if (DEP[_] <= DEP[z]) {
                l0 
= DEP[z] - DEP[_] + 1; r0 = DEP[y] - DEP[_];
                opr0(
0, tot[y] - 1, root[y]); break;
            } 
else {
                l0 
= 0; r0 = DEP[y] - DEP[_];
                opr0(
0, tot[y] - 1, root[y]); y = E[pr[_]].a;
            }
        }
    }
    re(i, n) vst[i] 
= 0;
    rre2(i, n, 
1) {
        x 
= Q[i];
        
if (E[pr[x]].Z && !vst[y = UP[x]]) {
            visit(
0, tot[x] - 1, root[x]); vst[y] = 1; _V[y] = V_tmp[0];
            
for (int j=x, k=tot[x]-1; j!=y; j=E[pr[j]].a, k--) _V[j] = V_tmp[k];
        }
    }
}
void pri()
{
    re2(i, 
1, n) if (_V[i] == INF) printf("%d\n"-1); else printf("%d\n", _V[i] - dist[i]);
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    
return 0;
}


2[Violet 6]故乡的梦
给出一个无向图,对于图中的每条边,求出当删掉它后,s-t最短路径。
做完了第【1】题之后,这题的解法就很容易想到了。
先求出这个图从s开始的SPT。显然,删掉它后s-t最短路径改变的边只能是这个SPT上的s-t割边。
考虑简单的情况:SPT是树。此时,s-t路上的一条边<u, v>删掉后,与第【1】题一样,整棵树分成ST两部分(sS部分,tT部分)。新的s-t最短路,必然是先从s沿着树边往下走到一个结点x,再经过一条<x, y>边走到T部分的一个点y,再从y走到t。可以证明,这个yt的最短路径必然是只经过T部分的点,不会重新回到S部分(否则直接从s走到这里就行了),因此,它必然不会经过<u, v>
SPT不是树,由于SPT中不管肿么走都是最短路径,可以求出它的一棵生成树(注意是有向生成树)。
这样,本题的算法就出来了:
<1>
求出st到每个点的最短距离distdist2,建立s开始的SPT,并求其任意一棵有向生成树;
<2>
求出SPT中的s-t割边(方法:求出有向生成树后,也就找到了一条s-t最短路,显然SPT中的s-t割边只能在这条最短路上。在SPT中删去这条路径,然后从s开始扫描路径上的每个点i,从i开始遍历删掉路径之后的SPT,若到达了这条路径上的点,维护其最大深度,扫描到点i时,若最大深度小于i(即i之后的点都还没被遍历到),则i的父边是s-t割边,否则不是。为了优化,可以共享vst——不管从哪个点开始,每个点只能被遍历一次),并标记;
<3>
在整个图中,枚举所有不在SPT的这棵生成树上的边(不一定不在SPT上!!)<x, y>(一条无向边拆成两条有向边),该边效果值为dist[x]+dist2[y]+边权,影响范围为[LCA(y, t), LCA(x, t))。由于影响范围都在s-t链上,因此就木有必要像【1】一样用路径剖分了,只需线段树即可。

代码:

#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<algorithm>
#include 
<queue>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
#define LCH(No) (No + 1)
#define RCH(No, l, r) (No + r - l + 2 - ((r ^ l) & 1))
const int MAXN = 200010, MAXM = 200010, MAXQ = 200010, MAXS = 19;
const ll INF = ~0Ull >> 2;
struct edge {
    
int a, b, w, pre, next;
    
bool Z;
} _E[MAXM 
+ MAXM + MAXN], E[MAXN << 1];
struct query {
    
int a, b;
    ll res;
} SQ[MAXQ];
struct pqnode {
    
int No;
    ll d0;
    
bool operator< (pqnode q0) const {return d0 > q0.d0;}
};
ll T[MAXN 
<< 1];
priority_queue 
<pqnode, vector<pqnode> > PQ;
int n, nq, n0, _m, m, s, t, Q[MAXN], pr0[MAXN], pr[MAXN], DEP[MAXN], ts[MAXN], prs[MAXN][MAXS], l0, r0;
ll dist[MAXN], dist2[MAXN], v0, res[MAXN];
bool vst[MAXN], vst2[MAXN];
void init_d()
{
    re(i, n) _E[i].pre 
= _E[i].next = E[i].pre = E[i].next = i; m = n; if (n & 1) _m = n + 1else _m = n;
}
void add_edge_(int a, int b, int w)
{
    _E[_m].a 
= a; _E[_m].b = b; _E[_m].w = w; _E[_m].pre = _E[a].pre; _E[_m].next = a; _E[a].pre = _m; _E[_E[_m].pre].next = _m++;
    _E[_m].a 
= b; _E[_m].b = a; _E[_m].w = w; _E[_m].pre = _E[b].pre; _E[_m].next = b; _E[b].pre = _m; _E[_E[_m].pre].next = _m++;
}
void add_edge(int a, int b, int w)
{
    E[m].a 
= a; E[m].b = b; E[m].w = w; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void init()
{
    
int m0, a0, b0, w0;
    scanf(
"%d%d"&n, &m0); init_d();
    re(i, m0) {scanf(
"%d%d%d"&a0, &b0, &w0); add_edge_(--a0, --b0, w0);}
    scanf(
"%d%d%d"&s, &t, &nq); s--; t--;
    re(i, nq) {scanf(
"%d%d"&SQ[i].a, &SQ[i].b); SQ[i].a--; SQ[i].b--; SQ[i].res = -1;}
}
void prepare()
{
    re(i, n) dist[i] 
= INF; dist[s] = 0; pqnode q0; q0.No = s; q0.d0 = 0; PQ.push(q0); int x, y; ll d0;
    
while (!PQ.empty()) {
        x 
= PQ.top().No; PQ.pop();
        
if (!vst[x]) {
            vst[x] 
= 1;
            
for (int p=_E[x].next; p != x; p=_E[p].next) {
                y 
= _E[p].b; d0 = dist[x] + _E[p].w;
                
if (d0 < dist[y]) {q0.d0 = dist[y] = d0; q0.No = y; PQ.push(q0);}
            }
        }
    }
    
if (dist[t] == INF) {re(i, nq) SQ[i].res = INF; return;}
    re(i, n) {dist2[i] 
= INF; vst[i] = 0;} dist2[t] = 0; q0.No = t; q0.d0 = 0; PQ.push(q0);
    
while (!PQ.empty()) {
        x 
= PQ.top().No; PQ.pop();
        
if (!vst[x]) {
            vst[x] 
= 1;
            
for (int p=_E[x].next; p != x; p=_E[p].next) {
                y 
= _E[p].b; d0 = dist2[x] + _E[p].w;
                
if (d0 < dist2[y]) {q0.d0 = dist2[y] = d0; q0.No = y; PQ.push(q0);}
            }
        }
    }
    re(i, n) vst[i] 
= 0; vst[s] = 1; Q[0= s; DEP[s] = 0;
    
for (int front=0, rear=0; front<=rear; front++) {
        x 
= Q[front];
        
for (int p=_E[x].next; p != x; p=_E[p].next) {
            y 
= _E[p].b;
            
if (dist[x] + _E[p].w == dist[y] && !vst[y]) {
                pr0[y] 
= p; pr[y] = m; add_edge(x, y, _E[p].w); DEP[y] = DEP[x] + 1; vst[y] = 1; Q[++rear] = y;
            }
        }
    }
    
int maxdep = 0, z; re(i, n) vst[i] = 0;
    n0 
= 0for (x=t; x!=s; x=E[pr[x]].a) {vst2[x] = 1; _E[pr0[x]].Z = _E[pr0[x] ^ 1].Z = 1; ts[n0++= x;} ts[n0++= s; vst2[s] = 1;
    
int _; for (int front=0, rear=n0-1; front<rear; front++, rear--) {_ = ts[front]; ts[front] = ts[rear]; ts[rear] = _;}
    re(i, n) {
        x 
= ts[i];
        
if (maxdep < i) E[pr[x]].Z = 1;
        Q[
0= x; vst[x] = 1;
        
for (int front=0, rear=0; front<=rear; front++) {
            y 
= Q[front];
            
for (int p=_E[y].next; p != y; p=_E[p].next) if (!_E[p].Z) {
                z 
= _E[p].b;
                
if (dist[y] + _E[p].w == dist[z] && !vst[z]) {vst[z] = 1; Q[++rear] = z; if (vst2[z] && DEP[z] > maxdep) maxdep = DEP[z];}
            }
        }
    }
    re(i, n) 
if (i == s) prs[i][0= -1else {prs[i][0= E[pr[i]].a; _E[pr0[i]].Z = _E[pr0[i] ^ 1].Z = 1;}
    re2(j, 
1, MAXS) re(i, n) if ((x = prs[i][j - 1]) == -1) prs[i][j] = -1else prs[i][j] = prs[x][j - 1];
    re2(i, 
1, n0 + n0) T[i] = INF;
}
int LCA(int x, int y)
{
    
if (DEP[x] > DEP[y]) {int _ = x; x = y; y = _;}
    
int dep0 = DEP[y] - DEP[x]; rre(i, MAXS) if ((1 << i) <= dep0) {y = prs[y][i]; dep0 -= (1 << i);}
    
if (x == y) return x; else {
        rre(i, MAXS) 
if (prs[x][i] != prs[y][i]) {x = prs[x][i]; y = prs[y][i];}
        
return E[pr[x]].a;
    }
}
int opr(int l, int r, int No)
{
    
if (l >= l0 && r <= r0) {if (v0 < T[No]) T[No] = v0;} else {
        
int mid = l + r >> 1;
        
if (mid >= l0) opr(l, mid, LCH(No));
        
if (mid < r0) opr(mid + 1, r, RCH(No, l, r));
    }
}
void visit(int l, int r, int No, ll minv)
{
    ll minv0 
= minv; if (T[No] < minv0) minv0 = T[No];
    
if (l == r) res[l] = minv0; else {
        
int mid = l + r >> 1;
        visit(l, mid, LCH(No), minv0);
        visit(mid 
+ 1, r, RCH(No, l, r), minv0);
    }
}
void solve()
{
    
int x, y;
    re2(i, (n 
& 1 ? n + 1 : n), _m) {
        x 
= _E[i].a; y = _E[i].b;
        
if (!_E[i].Z) {
            l0 
= DEP[LCA(x, t)] + 1; r0 = DEP[LCA(y, t)];
            
if (l0 <= r0) {
                v0 
= dist[x] + _E[i].w + dist2[y];
                opr(
0, n0 - 11);
            }
        }
    }
    visit(
0, n0 - 11, INF);
    re(i, nq) {
        x 
= SQ[i].a; y = SQ[i].b;
        
if (vst2[x] && vst2[y]) {
            
if (DEP[x] + 1 == DEP[y] && E[pr[y]].Z) SQ[i].res = res[DEP[y]];
            
else if (DEP[y] + 1 == DEP[x] && E[pr[x]].Z) SQ[i].res = res[DEP[x]];
            
else SQ[i].res = dist[t];
        } 
else SQ[i].res = dist[t];
    }
}
void pri()
{
    re(i, nq) 
if (SQ[i].res == INF) puts("Infinity"); else printf("%lld\n", SQ[i].res);
}
int main()
{
    init();
    prepare();
    
if (dist[t] != INF) solve();
    pri();
    
return 0;
}


 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理