傳送門

十分顯然完成工作的時(shí)間和航耗時(shí)最長的運(yùn)輸計(jì)劃有關(guān)

所以題目意思就是要求最大值最小

所以可以想到二分

把所有大于mid時(shí)間的航線打上標(biāo)記，顯然刪邊只能在所有這些航線的公共路徑上

要如何快速打標(biāo)記是個(gè)問題

二分已經(jīng)有一個(gè)log，所以只能承受O(n)的判斷

如果能知道一條邊的經(jīng)過次數(shù)，那么就知道這條邊是否在公共路徑上

容易想到樹上差分，預(yù)處理一波 lca 后復(fù)雜度可行

刪邊肯定貪心地刪能刪的最長邊

要如何判斷刪邊后是否最長路徑小于mid呢

顯然可以預(yù)處理出不刪前的最長路徑

如果最長路徑減去刪的邊 ≤ mid 那么其他路徑減刪去的邊肯定不大于mid（注意刪去的邊在所有原長超過mid的路徑上）

至于其他原長小于 mid 的路徑根本不用考慮

所以總結(jié)一下就是二分+樹上差分

luogu第13個(gè)點(diǎn)真是用sang心xin良bing苦kuang，把復(fù)雜度卡滿了

求LCA可能用樹剖會(huì)快一點(diǎn)，然而懶得寫...

#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> using namespace std; inline int read() {register int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f; } const int N=3e5+7; int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt; inline void add(int &a,int &b,int &c) {from[++cntt]=fir[a];fir[a]=cntt; to[cntt]=b; val[cntt]=c; }int f[N][21],dep[N],dis[N],frm[N];//f和dep用來求LCA,dis是點(diǎn)到根的距離，用來求最長路徑,frm是連接父節(jié)點(diǎn)的邊的編號(hào) void dfs1(int &x,int &fa)//第一遍dfs處理f,dep,dis,frm {f[x][0]=fa; dep[x]=dep[fa]+1;for(int i=1;i<=19;i++) f[x][i]=f[f[x][i-1]][i-1];for(int i=fir[x];i;i=from[i]){int &v=to[i]; if(v==fa) continue;dis[v]=dis[x]+val[i]; frm[v]=i; dfs1(v,x);} } inline int LCA(int x,int y)//求LCA {if(dep[x]<dep[y]) swap(x,y);for(int i=19;i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];return f[x][0]; }int n,m,cnt[N],lca[N],sum[N],tot,mxlen,rt=1; //cnt是差分?jǐn)?shù)組，lca顧名思義,sum[i]是第i條路徑的長度,tot記錄有幾條邊原長大于mid,mxlen是最長路徑長度,rt是根節(jié)點(diǎn) struct data {int a,b; }d[N];//存運(yùn)輸計(jì)劃 int pos;//記錄最長邊的編號(hào) void dfs2(int &x)//dfs2處理每條邊經(jīng)過次數(shù) {for(int i=fir[x];i;i=from[i]){int &v=to[i]; if(v==f[x][0]) continue;dfs2(v); cnt[x]+=cnt[v];}if(cnt[x]==tot&&val[frm[x]]>val[pos]) pos=frm[x];//如果當(dāng)前節(jié)點(diǎn)被所有大于mid的邊經(jīng)過則考慮更新pos } inline bool pd(int &p)//判斷合法性，p就是mid {tot=pos=0; memset(cnt,0,sizeof(cnt));//初始化for(register int i=1;i<=m;i++){if(sum[i]<=p) continue;cnt[d[i].a]++; cnt[d[i].b]++;cnt[lca[i]]-=2;tot++;//記錄差分 }dfs2(rt);return mxlen-val[pos]>p ? 0 : 1;//判斷 }int main() {int a,b,c;n=read(); m=read();for(register int i=1;i<n;i++){a=read(),b=read(),c=read();add(a,b,c); add(b,a,c);}dfs1(rt,rt);for(register int i=1;i<=m;i++){d[i].a=read(); d[i].b=read();lca[i]=LCA(d[i].a,d[i].b);//預(yù)處理lcasum[i]=dis[d[i].a]+dis[d[i].b]-(dis[lca[i]]<<1);//求出summxlen=max(mxlen,sum[i]);//嘗試更新maxlen }register int l=0,r=mxlen,mid;while(l<=r){mid=l+r>>1;pd(mid) ? r=mid-1 : l=mid+1;}printf("%d",l);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LLTYYC/p/9828248.html

總結(jié)

以上是生活随笔為你收集整理的P2680 运输计划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。