題目鏈接：P2680 [NOIP2015 提高組] 運輸計劃 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
看了好長時間題解才終于懂的，有關lca和二分答案的題解解釋的不詳細，一時半會理解不過來，于是自己寫一篇解釋盡管解釋主要在代碼中，希望能對迷茫的小伙伴有幫助
決議（主要為二分答案的決議，lca只是求距離和找覆寫邊時用得到，這里不多說）：
由于m個運輸計劃是同時出發，所以所需要的時間取決于花費最長的時間，因為一個任務在y分鐘內完成，那么另一個任務x(x<=y)也一定完成，
問題就轉化成了求最長邊最短，二分答案，
接下來，就是怎么二分了
想讓時間大于答案的任務的時間減小，題目里說了，可以設一條邊為蟲洞，我們就找這個任務里哪條（些）邊可以設為蟲洞,這條（些）邊就是被覆寫的邊，我們將它們記錄一下，所以我們只要找這些超時的任務的公共覆寫邊就好了，即這條（些）邊被記錄的次數等于超時的任務數
代碼有詳細注釋，不懂可以去看一下代碼
#include<bits/stdc++.h> #define ll long long #define rll register long long using namespace std; const ll N=3e5+5; ll n,m,cnt; ll h[N],lg[N],sum[N],deep[N],st[N][20],vis[N],up[N]; struct edge//邊 { ll v,w,nxt; } e[N<<1]; struct rw//任務 { ll u,v,lca,dis; bool operator <(const rw x)//多載運算子 { return dis<x.dis; } } g[N]; inline ll read() { ll x=0; bool flag=false; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') flag=true; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return flag?~x+1:x; } void add(ll u,ll v,ll w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].nxt=h[u]; h[u]=cnt; } void dfs(ll u,ll fat) { deep[u]=deep[fat]+1;//深度更新 st[u][0]=fat;//更新st表 for(rll i=1;i<=lg[deep[u]];++i) { st[u][i]=st[st[u][i-1]][i-1];//更新st表 } for(rll i=h[u];i;i=e[i].nxt)//遍歷 { ll v=e[i].v,w=e[i].w; if(v!=fat)//如果不是父節點 { sum[v]=(sum[u]+w); //到根節點的距離就是父節點到根節點的距離加上這條邊的邊權 up[v]=w;//處理到父節點的距離 dfs(v,u);//繼續搜索 } } } ll LCA(ll x,ll y)//正常求LCA { if(deep[x]<deep[y]) { x=x^y,y=x^y,x=x^y;//位運算版本的交換 } while(deep[x]>deep[y]) { x=st[x][lg[deep[x]-deep[y]]-1];//讓兩點在同一深度 } if(x==y) return x; for(rll i=lg[deep[x]]-1;i>=0;--i)//找交匯之前最后到達的點 { if(st[x][i]!=st[y][i])//如果不相交,向上跳 { x=st[x][i]; y=st[y][i]; } } return st[x][0];//回傳lca } bool check(ll len) { if(g[m].dis<=len) return true; //如果路程最長的都比不過當前二分的答案,那么這個答案是可行的,直接回傳 for(rll i=1;i<=n;++i) vis[i]=0;//每次操作前,陣列清0 ll cont=0,maxn=0; //cont 記錄比當前答案大的邊,maxn記錄被覆寫次數最多的邊被覆寫的次數 //(我知道maxn這里我解釋的很trouble，不好理解就把他看成每條邊被覆寫的次數的最大值) //一定要時刻記住maxn的含義!!! for(rll i=m;i>=1;--i)//遍歷 { if(g[i].dis<=len) break; //如果當前任務的路程已經小于答案，就沒必要繼續遍歷查找了，退出即可 cont++;//當前任務路程比答案大，計數器+1 ll u=g[i].u,v=g[i].v,lca=g[i].lca,c=g[i].dis-len; //c 如果這條邊大于或等于c，就說明刪去它，這個任務的時間就小于或等于答案 //即這條邊可以設為蟲洞 while(u!=lca)//如果起點不是lca,那就向上找，查詢被覆寫的邊 { if(up[u]>=c)//大于c,說明在這個任務中,它可以設為蟲洞，也就是上文說的覆寫 { vis[u]++; maxn=max(maxn,vis[u]);//更新maxn } u=st[u][0];//往上慢慢找,時間限制是1s~2s } while(v!=lca)//如果終點不是lca,向上找 { if(up[v]>=c)//和上面一樣 { vis[v]++; maxn=max(maxn,vis[v]);//更新maxn } v=st[v][0];//慢慢跳(～￣▽￣)～ } if(maxn<cont)return false; //這里maxn只能小于等于cont,因為進行了cont次回圈，一條邊最多被覆寫cont次 //maxn是邊被覆寫的次數的最大值 //如果小于cont,就說明找不到一條邊可以被刪去后使任務的時間小于等于答案 //所以這個答案不成立 //如果maxn==cont 就說明至少有一條邊可以做到刪去后使任務的時間小于等于答案 } return true; } int main() { n=read(),m=read(); for(rll i=1;i<n;++i) { ll x=read(),y=read(),z=read(); add(x,y,z); add(y,x,z); } for(rll i=1;i<=n;++i) { lg[i]=lg[i-1]+(1<<lg[i-1]==i);//預處理log,節約時間 } dfs(1,0);//搜索 for(rll i=1;i<=m;++i)//記錄每一個計劃的資訊 { ll u=read(),v=read(),lca=LCA(u,v); g[i].u=u;//起點 g[i].v=v;//終點 g[i].lca=lca;//lca g[i].dis=sum[u]+sum[v]-(sum[lca]<<1);//這個計劃的長度 } sort(g+1,g+m+1);//將任務從小到大排序 ll l=0,r=3e8,ans; while(l<r) //注意!!!這里二分的是最終答案,也就是最小花費時間,清楚概念,否則后邊就和我一樣容易混 { ll mid=(l+r)>>1;//二分操作 if(check(mid)) r=mid,ans=mid; else l=mid+1; } printf("%lld\n",ans); return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/498404.html
標籤：C++
下一篇：C++質數判斷演算法的時間測驗