网站信息化建设领导小组,西安网站建设动力无限,奢侈品电商网站首页设计,网站建设所需软件传送门 十分显然完成工作的时间和航耗时最长的运输计划有关 所以题目意思就是要求最大值最小 所以可以想到二分 把所有大于mid时间的航线打上标记#xff0c;显然删边只能在所有这些航线的公共路径上 要如何快速打标记是个问题 二分已经有一个log#xff0c;所以只能承受O(n)…传送门 十分显然完成工作的时间和航耗时最长的运输计划有关 所以题目意思就是要求最大值最小 所以可以想到二分 把所有大于mid时间的航线打上标记显然删边只能在所有这些航线的公共路径上 要如何快速打标记是个问题 二分已经有一个log所以只能承受O(n)的判断 如果能知道一条边的经过次数那么就知道这条边是否在公共路径上 容易想到树上差分预处理一波 lca 后复杂度可行 删边肯定贪心地删能删的最长边 要如何判断删边后是否最长路径小于mid呢 显然可以预处理出不删前的最长路径 如果最长路径减去删的边 ≤ mid 那么其他路径减删去的边肯定不大于mid注意删去的边在所有原长超过mid的路径上 至于其他原长小于 mid 的路径根本不用考虑 所以总结一下就是二分树上差分 luogu第13个点真是用sang心xin良bing苦kuang把复杂度卡满了 求LCA可能用树剖会快一点然而懒得写... #includeiostream
#includealgorithm
#includecstdio
#includecmath
#includecstring
using namespace std;
inline int read()
{register int x0,f1; char chgetchar();while(ch0||ch9) { if(ch-) f-1; chgetchar(); }while(ch0ch9) { x(x1)(x3)(ch^48); chgetchar(); }return x*f;
}
const int N3e57;
int fir[N],from[N1],to[N1],val[N1],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是点到根的距离用来求最长路径,frm是连接父节点的边的编号
void dfs1(int x,int fa)//第一遍dfs处理f,dep,dis,frm
{f[x][0]fa; dep[x]dep[fa]1;for(int i1;i19;i) f[x][i]f[f[x][i-1]][i-1];for(int ifir[x];i;ifrom[i]){int vto[i]; if(vfa) 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 i19;i0;i--)if(dep[f[x][i]]dep[y]) xf[x][i];if(xy) return x;for(int i19;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}int n,m,cnt[N],lca[N],sum[N],tot,mxlen,rt1;
//cnt是差分数组lca顾名思义,sum[i]是第i条路径的长度,tot记录有几条边原长大于mid,mxlen是最长路径长度,rt是根节点
struct data
{int a,b;
}d[N];//存运输计划
int pos;//记录最长边的编号
void dfs2(int x)//dfs2处理每条边经过次数
{for(int ifir[x];i;ifrom[i]){int vto[i]; if(vf[x][0]) continue;dfs2(v); cnt[x]cnt[v];}if(cnt[x]totval[frm[x]]val[pos]) posfrm[x];//如果当前节点被所有大于mid的边经过则考虑更新pos
}
inline bool pd(int p)//判断合法性p就是mid
{totpos0; memset(cnt,0,sizeof(cnt));//初始化for(register int i1;im;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;nread(); mread();for(register int i1;in;i){aread(),bread(),cread();add(a,b,c); add(b,a,c);}dfs1(rt,rt);for(register int i1;im;i){d[i].aread(); d[i].bread();lca[i]LCA(d[i].a,d[i].b);//预处理lcasum[i]dis[d[i].a]dis[d[i].b]-(dis[lca[i]]1);//求出summxlenmax(mxlen,sum[i]);//尝试更新maxlen}register int l0,rmxlen,mid;while(lr){midlr1;pd(mid) ? rmid-1 : lmid1;}printf(%d,l);return 0;
} 转载于:https://www.cnblogs.com/LLTYYC/p/9828248.html
