网站建设伍金手指下拉8公众号和网站

网站建设伍金手指下拉8,公众号和网站,知名的环保行业网站开发,社交网站上的商城怎么做本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来#xff0c;并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构#xff0c;旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。 欢迎大…本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing1170. 排队布局 - AcWing题库【题目描述】当排队等候喂食时奶牛喜欢和它们的朋友站得靠近些。农夫约翰有N NN头奶牛编号从1 11到N NN沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条所以可能有两头或者更多奶牛站在同一位置上。如果我们想象奶牛是站在一条数轴上的话允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好感它们希望两者之间的距离不超过一个给定的数L LL。另一方面一些奶牛相互间非常反感它们希望两者间的距离不小于一个给定的数D DD。给出M L M_LML​条关于两头奶牛间有好感的描述再给出M D M_DMD​条关于两头奶牛间存有反感的描述。你的工作是如果不存在满足要求的方案输出-1如果1 11号奶牛和N NN号奶牛间的距离可以任意大输出-2否则计算出在满足所有要求的情况下1 11号奶牛和N NN号奶牛间可能的最大距离。【输入】第一行包含三个整数N , M L , M D N,M_L,M_DN,ML​,MD​。接下来M L M_LML​行每行包含三个正整数A , B , L A,B,LA,B,L表示奶牛A AA和奶牛B BB至多相隔L LL的距离。再接下来M D M_DMD​行每行包含三个正整数A , B , D A,B,DA,B,D表示奶牛A AA和奶牛B BB至少相隔D DD的距离。【输出】输出一个整数如果不存在满足要求的方案输出-1如果1 11号奶牛和N NN号奶牛间的距离可以任意大输出-2否则输出在满足所有要求的情况下1 11号奶牛和N NN号奶牛间可能的最大距离。【输入样例】4 2 1 1 3 10 2 4 20 2 3 3【输出样例】27【算法标签】《AcWing 1170 排队布局》 #SPFA# #差分约束#【代码详解】#includebits/stdc.husingnamespacestd;constintN1005,M21005,INF0x3f3f3f3f;// 最大顶点数、边数、无穷大intn,m1,m2;// n: 顶点数, m1: 第一类边数, m2: 第二类边数inth[N],e[M],w[M],ne[M],idx;// 链式前向星存储图intdist[N];// 最短距离数组intcnt[N];// 松弛计数数组用于检测负环boolst[N];// 标记顶点是否在队列中/** * 添加有向边 * param a 起点 * param b 终点 * param c 权重 */voidadd(inta,intb,intc){e[idx]b;// 边指向的顶点w[idx]c;// 边的权重ne[idx]h[a];// 指向原链表头h[a]idx;// 更新头指针}/** * SPFA算法检测负环并计算最短路径 * 从size个顶点开始检测图中是否存在负环 * param size 入队的顶点数量 * return 存在负环返回false否则返回true */boolspfa(intsize){// 初始化memset(dist,0x3f,sizeof(dist));// 距离初始化为无穷大memset(st,0,sizeof(st));// 标记数组清零memset(cnt,0,sizeof(cnt));// 松弛计数清零queueintq;// SPFA队列// 将前size个顶点入队for(inti1;isize;i){dist[i]0;// 距离设为0相当于超级源点q.push(i);// 顶点入队st[i]true;// 标记在队列中}// SPFA主循环while(!q.empty()){inttq.front();// 取出队首顶点q.pop();st[t]false;// 标记不在队列中// 遍历t的所有邻接边for(intih[t];i!-1;ine[i]){intje[i];// 邻接顶点// 松弛操作if(dist[j]dist[t]w[i]){dist[j]dist[t]w[i];// 更新最短距离cnt[j]cnt[t]1;// 松弛次数1// 如果顶点j被松弛了n次说明存在负环if(cnt[j]n){returnfalse;// 存在负环}// 如果j不在队列中入队if(!st[j]){q.push(j);st[j]true;}}}}returntrue;// 不存在负环}intmain(){// 输入顶点数、第一类边数、第二类边数cinnm1m2;// 初始化邻接表memset(h,-1,sizeof(h));// 添加基础约束边x_{i1} ≥ x_i// 即x_i - x_{i1} ≤ 0// 建边i1 → i权重0for(inti1;in;i){add(i1,i,0);}// 处理第一类边x_b - x_a ≤ cwhile(m1--){inta,b,c;cinabc;// 确保a ≤ bif(ba){swap(a,b);}// 约束x_b - x_a ≤ c// 建边a → b权重cadd(a,b,c);}// 处理第二类边x_b - x_a ≥ cwhile(m2--){inta,b,c;cinabc;// 确保a ≤ bif(ba){swap(a,b);}// 约束x_b - x_a ≥ c// 等价于x_a - x_b ≤ -c// 建边b → a权重-cadd(b,a,-c);}// 检测是否存在负环if(!spfa(n))// 从所有顶点开始检测{puts(-1);// 存在负环无解}else{// 计算从顶点1到顶点n的最短路径spfa(1);// 从顶点1开始// 如果dist[n]为无穷大说明不可达if(dist[n]INF){puts(-2);}else{coutdist[n]endl;// 输出最短距离}}return0;}【运行结果】4 2 1 1 3 10 2 4 20 2 3 3 27