CF733F Drivers Dissatisfaction 题解

# 0.闲聊几句 [--->卑微的题面](https://www.luogu.com.cn/problem/CF733F) [博客食用更佳>-<](https://www.luogu.com.cn/blog/Silymtics/cf733f-drivers-dissatisfaction-ti-xie) ------------ # 1.Solution 主要思路：[最小生成树](https://www.luogu.com.cn/problem/P3366) + [$\text{LCA}$](https://www.luogu.com.cn/problem/P3379) + （感觉和[严格次小生成树](https://www.luogu.com.cn/problem/P4180)有点像） 根据题意我们需要先用 $\text{Kruskal}$ 建出一棵最小生成树 我们考虑枚举每一条边来确定降低那条边的权值更优。 为什么只需要枚举一条边？ 假设现在有两条边 $e_1,e_2$，如果 $e_1 > e_2$ 那么不断的减 $e_2$ 一定更优，这样赚便宜。如果 $e_1 = e_2$ 那么减那条边都可以，既然都可以，把所有的操作都放在一个边上岂不是更简单？ 现在讨论每一条边， - 如果是在树上的边： 直接把所有钱都砸在这条边上（~~money 的力量~~），看看得到的最小生成树权值和是否会更小 - 如果是非树边： 同样是把所有钱都砸在这条边上，这条边就会有一个新的权值。 因为连接这条边会使原来的生成树出现一个环，那么需要我们删掉环上的一条边。根据贪心的策略，我们找到最大的边删除。然后判断此时生成树的权值和是否更小。如果更小就更新答案。 直接枚举边做出判断是难以实现的,这就需要我们预处理最大值。 倍增预处理或者直接裸上树链剖分都可以。 再按照上面的思路跑一遍。 最后输出答案（可能有多组解）。 ### 提几点注意事项（感谢Aliemo学姐为我debug）： 1、代码中有除法时要保证除数不为零，否则会RE，就像我  2、看好题目中 $ans$ 最大值可能为多少（ $2 \times 10^{14}$ !!!），所以用到 $\text{INF}$ 的时候要开大一点（开 $10^{18}$ 就足够） 3、注意不同图（树）中的边号所存的边号到底是排序前的边号，还是排序后的边号 # 2.放代码 （~~~~我知道你们只喜欢这个~~~~） ## 2.1 关于变量名的解释： ```cpp /* edge{ 起点，终点 权值w，花费c，边号（排序后），下一条边 }e[]：生成树的边 ,a[]：输入的边 node{ 边号，边的权值 } maxm[][]：用来存编号及边的权值（倍增里存的最大值 n:点数 m:边数 S:钱数（花费 ans：存答案 cnt：通过kruskal建出的生成树的权值和 flag：标记减那一条边更优 pre_jia:上一次加的边 pre_jian: 上一次减的边 c[]：每条边减权值所需的花费 w[]：每条边的权值 fa[]：每个点的父亲（kruskal的并查集） f[][]：倍增惯用的小抄 depth[]：每个点的深度（LCA惯用数组） vise[]:标记 用kruskal建完树 后有那几条边被选中 vis_new[]: 标记 用过减边权的边 后有那几条边被选中 */ ``` ## 2.2 真正的AC代码： ```cpp #include<iostream> #include<cstdio> #include<algorithm> #define LL long long #define INF 1e18 using namespace std; const int MAXN = 2e5+5; struct edge{ int from,to; LL w,c,bh,nxt; bool operator < (const edge &b) const {return w < b.w ;} }e[MAXN << 2],a[MAXN << 2]; struct node{ int bh;LL dis; }maxm[MAXN][26];//maxm用来存编号及边的权值 int head[MAXN << 2], num_edge; LL n, m, S, ans, cnt, flag, pre_jia, pre_jian; int c[MAXN], w[MAXN]; LL fa[MAXN];//并查集 LL f[MAXN][26];//倍增 LL depth[MAXN];//存深度 bool vise[MAXN << 1],vis_new[MAXN << 1];//vise标记在最小生成树中的边，vis_new标记更换过的边 LL find(LL x) {return fa[x] == x ? x : fa[x] = find(fa[x]); } void add(int from,int to,LL w,LL c, LL i){ e[++num_edge].from = from; e[num_edge].to = to; e[num_edge].w = w; e[num_edge].c = c; e[num_edge].bh = i; e[num_edge].nxt = head[from]; // e[num_edge] = (edge){from, to, w, c, i, head[from]}; head[from] = num_edge; } void kruskal(){ for(int i=1;i<=m;++i){ LL uf = find(a[i].from), vf = find(a[i].to); if(uf != vf){ add(a[i].from,a[i].to,a[i].w,a[i].c,i); add(a[i].to,a[i].from,a[i].w,a[i].c,i);//加边是排序后的编号 fa[uf] = vf; cnt += a[i].w; vise[i] = 1; vis_new[i] = 1; } } } void dfs(LL u,LL fa){//在建出的最小生成树上跑DFS，并对LCA进行初始化 f[u][0] = fa; //cout<<u<<" "<<fa<<"lzx"<<endl; for(int i=head[u]; i; i = e[i].nxt){ LL v = e[i].to; if(v == fa) continue; else{ depth[v] = depth[u] + 1ll; maxm[v][0].dis = e[i].w; maxm[v][0].bh = e[i].bh;//a中排序后的编号 dfs(v,u); } } } void init_lca(){ for(int i=1;i<=25;++i){ for(int j = 1; j <= n; ++j){ //cout<<f[j][0]<<"fjh"<<endl; f[j][i] = f[f[j][i-1]][i-1];//LCA初始化 if(maxm[j][i-1].dis > maxm[f[j][i-1]][i-1].dis){ maxm[j][i].dis = maxm[j][i-1].dis;//存向上跳2^i步的最大值 maxm[j][i].bh = maxm[j][i-1].bh;//及编号 } else{ maxm[j][i].dis = maxm[f[j][i-1]][i-1].dis; maxm[j][i].bh = maxm[f[j][i-1]][i-1].bh; } } } } LL get_lca(LL u,LL v){ if(depth[u] > depth[v]) swap(u,v);//保证v的深度大于u的深度 for(int i = 25; i >= 0; --i){//把v点调到和u点同样的位置 if(depth[f[v][i]] < depth[u]) continue; else v = f[v][i]; } if(u == v) return u;//如果此时是同一个点，直接返回即可 for(int i = 25; i >= 0; --i){//两个点一起向上跳，跳到最近公共祖先的下面 if(f[v][i] != f[u][i]){ v = f[v][i]; u = f[u][i]; } } //cout<<u<<"wzd"<<endl; return f[u][0];//再跳一下 } node qmax(LL u, LL v){ node Ans; Ans.bh = -1; Ans.dis = -INF; for(int i = 25; i >= 0; --i){ if(depth[f[u][i]] >= depth[v]){ if(Ans.dis < maxm[u][i].dis){//如果珂跳到最近公共祖先的下面，尝试更新最大值 Ans.dis = maxm[u][i].dis; Ans.bh = maxm[u][i].bh; } u = f[u][i];//向上跳一下 } } return Ans;//返回Ans值 } int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=m;++i) scanf("%d",&w[i]); for(int i=1;i<=m;++i) scanf("%d",&c[i]); for(int i=1,u,v;i<=m;++i){//存边 scanf("%d%d",&u,&v); a[i].from = u; a[i].to = v; a[i].w = w[i]; a[i].c = c[i]; a[i].bh = i;//a[i].bh存的是一开始的边号 } scanf("%lld",&S); for(int i=1;i<=n;++i) fa[i] = i; sort(a+1,a+m+1);//i与a[i].bh已经不一样了 kruskal(); depth[1] = 1; maxm[1][0].dis = -INF; maxm[1][0].bh = e[1].bh; dfs(1,1);//深搜初始化LCA init_lca();//初始化LCA ans = INF; for(int i=1;i<=m;++i){ LL ww = S / a[i].c; if(vise[i]){//如果这条边是最小生成树里面的，直接减去即可 if(ans > cnt - ww){ flag = i; //更新要减权值的bian } ans = min(ans, cnt - ww); } else{ LL u = a[i].from, v = a[i].to; LL lca = get_lca(u,v);//u，v的LCA node maxu = qmax(u, lca);//两边的最大值都要求 node maxv = qmax(v, lca); if(maxu.dis > maxv.dis){//挑有最大边最大的那一边 if(ans > cnt - maxu.dis + a[i].w - ww){ //删掉最长的那个边，加上新来的那条边，减去可以减得边权值 ans = cnt - maxu.dis + a[i].w - ww; vis_new[pre_jia] = 0; vis_new[pre_jian] = 1; vis_new[i] = 1;//把新加的标记一下 vis_new[maxu.bh] = 0;//把删掉的标记为0 pre_jia = i; pre_jian = maxu.bh;//这里都是a中排序后的边号 flag = i;//更新一下标记bian } } else{ if(ans > cnt - maxv.dis + a[i].w - ww){ ans = cnt - maxv.dis + a[i].w - ww; vis_new[pre_jia] = 0; vis_new[pre_jian] = 1; vis_new[i] = 1; vis_new[maxv.bh] = 0; pre_jia = i; pre_jian = maxv.bh;//这里也是排序后的边号 flag = i;//更新一下标记bian } } } //if(pre_jian == 1){ // cout<<"lkp"<<endl; // } // if( vis_new[1] == 0){ // printf("bj\n"); // } } if(flag)//防止除数为0 a[flag].w = a[flag].w - (S / a[flag].c); printf("%lld\n",ans); for(int i = 1; i <= m; ++i){ if(vis_new[i]){//如果这条边在新树中被标记过，就输出 printf("%lld %lld\n", a[i].bh, a[i].w); } } return 0; } ``` ## 2.3 附：我遇到的多组解： 样例一题面输出： ```cpp 0 1 1 3 1 6 1 7 2 8 -5 ``` 我的输出（不同但是过了）： ```cpp 0 1 1 4 1 6 1 7 2 8 -5 ``` 手膜样例之后发现其实都是一组合法解，需要自己注意一下。 （~~样例不对不要慌，万一交上去AC了呢~~） ------------ # 3.写在最后 第一次写黑题题解（~~现在掉紫了~~），由于细节太多，难免有些遗漏 如果您有什么疑惑，或我犯了什么sb错误，尽管提出 $\text{The\ end.}$