Binary search is USEFUL!

題目鏈接：1307D - Cow and Fields

題目大意：給定一個(gè) \(n\) 個(gè)點(diǎn) \(m\) 條邊的簡(jiǎn)單無(wú)向連通圖，并指定 \(k\) 個(gè)特殊點(diǎn)。要求在特殊點(diǎn)之間加一條邊使得從 \(1\) 到 \(n\) 的最短路最大，輸出這個(gè)最大值。

一般這種題有一個(gè)通用的套路就是以起點(diǎn)和終點(diǎn)為源點(diǎn)各跑一次單源最短路，在這題里我們直接 \(\texttt{BFS}\) 即可。這樣我們就能對(duì)每個(gè)點(diǎn) \(i\) 求出其到點(diǎn) \(1\) 的距離 \(dis(1,i)\) 與到點(diǎn) \(n\) 的距離 \(dis(n,i)\)。接著我們就需要考慮加入一條邊 \((s,t)\) 產(chǎn)生的貢獻(xiàn)，其為 min(dis[1][s]+dis[t][n],dis[1][t]+dis[s][n])+1。我們的目的就是最大化這個(gè)貢獻(xiàn)，這樣就能讓結(jié)果的最短路盡可能大。這里我們采用一個(gè) useful 的算法，也就是二分來(lái)解決這個(gè)問(wèn)題。

二分貢獻(xiàn)的值 \(w\)，那么我們要做的就是判斷是否存在 \(s,t\) 使得 min(dis[1][s]+dis[t][n],dis[1][t]+dis[s][n])+1>=w 成立，那么就是要讓括號(hào)內(nèi)的兩項(xiàng)同時(shí)大于等于 \(w-1\)。我們進(jìn)行移項(xiàng)，會(huì)得到我們要判斷的式子實(shí)際上就是：

那么我們枚舉 \(s\)，把 \(dis(t,n)\) 和 \(dis(t,1)\) 看成與 \(t\) 有關(guān)的兩個(gè)數(shù)組 \(a,b\)。就變成了每次要判斷是否存在 \(t\) 使得 a[t]>=w1 && b[t]>=w2 成立。

那么采用求解二維偏序同樣的技巧，我們?cè)诿杜e \(s\) 的時(shí)候，按照 \(dis(s,1)\) 升序的規(guī)律枚舉，并同樣地把 \(t\) 按照 \(dis(t,n)\) 降序排列。這樣就能做到每次詢問(wèn)時(shí)，\(w_1\) 的值是單調(diào)下降的，那么就使用雙指針，把滿足 $a_t\ge w_1 $ 的 \(t\) 對(duì)應(yīng)的 \(b_t\) 加進(jìn)來(lái)，之后再判斷是否存在 $b_t \ge w_2 $ 即可。使用樹狀數(shù)組維護(hù)的話時(shí)間復(fù)雜度為 \(O(n\log ^2n)\)，雖然是雙 \(\log\) 但是跑得飛快。需要注意的是由于不能加一個(gè)自環(huán)進(jìn)去，所以需要在枚舉到 \(s\) 時(shí)要暫時(shí)把 \(b_s\) 的貢獻(xiàn)去掉（如果此時(shí) \(b_s\) 被加到了樹狀數(shù)組內(nèi)）。

但注意到，實(shí)際上我們最后只需要判斷一個(gè)存在性，所以只需要在過(guò)程中維護(hù) \(b_t\) 的最大值和次大值（為了維護(hù)去掉 \(b_s\) 的情況）即可，時(shí)間復(fù)雜度 \(O(n\log n)\)。雖然實(shí)踐證明加了這個(gè)優(yōu)化后反而跑得更慢了（草。

\(O(n\log ^2n)\)的代碼如下，不要忘了最后要和原本的最短路取 \(\min\)：

#include<bits/stdc++.h>
using namespace std;
#define N 200020
#define mp make_pair
int n,m,k,dis[N][2];
vector<int>d[N],t,e;
struct BIT
{
    int t[N],cnt;
    int lowbit(int x){return x&(-x);}
    void init(){cnt=0;memset(t,0,sizeof(t));}
    void cg(int x,int c){cnt+=c;while(x<N)t[x]+=c,x+=lowbit(x);}
    int ask(int x){int r=0;while(x)r+=t[x],x-=lowbit(x);return r;}
    int Q(int x){return ask(max(x-1,0))<cnt;}
}T;
bool cmp(int x,int y){return dis[x][0]<dis[y][0];}
bool cmp2(int x,int y){return dis[x][1]>dis[y][1];}
void BFS(int st,int o)
{
    queue<int>q;
    q.push(st);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(auto y:d[x])if(!dis[y][o] && y!=st){
            dis[y][o]=dis[x][o]+1;
            q.push(y);
        }
    }
}
bool check(int w)
{
    int i=0;
    T.init();
    for(auto s:t){
        int w1=w-dis[s][0]-1;
        while(i<k && dis[e[i]][1]>=w1)
            T.cg(dis[e[i]][0]+1,1),i++;
        if(dis[s][1]>=w1)T.cg(dis[s][0]+1,-1);
        if(T.Q(w-dis[s][1]))return true;
        if(dis[s][1]>=w1)T.cg(dis[s][0]+1,1);
    }
    return false;
}
int Useful()
{
    int l=1,r=dis[n][0],mid;
    while(l<r){
        mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    return l;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++){
        int x;
        scanf("%d",&x);
        t.push_back(x);
        e.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        d[u].push_back(v);
        d[v].push_back(u);
    }
    BFS(1,0),BFS(n,1);
    sort(t.begin(),t.end(),cmp);
    sort(e.begin(),e.end(),cmp2);
    printf("%d\n",min(dis[1][1],Useful()));
}

名言警句：Stop learning useless algorithms, go and solve some problems, learn how to use binary search.