医院网站详细设计做加盟童装交流网站

医院网站详细设计,做加盟童装交流网站,服务网点网站建设,做电商网站企业本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来#xff0c;并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构#xff0c;旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。 欢迎大…本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P5960 【模板】差分约束 - 洛谷【题目描述】给出一组包含m mm个不等式有n nn个未知数的形如{ x c 1 − x c 1 ′ ≤ y 1 x c 2 − x c 2 ′ ≤ y 2 ⋯ x c m − x c m ′ ≤ y m \begin{cases} x_{c_1}-x_{c_1}\leq y_1 \\x_{c_2}-x_{c_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c_m}\leq y_m\end{cases}⎩⎨⎧​xc1​​−xc1′​​≤y1​xc2​​−xc2′​​≤y2​⋯xcm​​−xcm′​​≤ym​​的不等式组求任意一组满足这个不等式组的解。【输入】第一行为两个正整数n , m n,mn,m代表未知数的数量和不等式的数量。接下来m mm行每行包含三个整数c , c ′ , y c,c,yc,c′,y代表一个不等式x c − x c ′ ≤ y x_c-x_{c}\leq yxc​−xc′​≤y。【输出】一行n nn个数表示x 1 , x 2 ⋯ x n x_1 , x_2 \cdots x_nx1​,x2​⋯xn​的一组可行解如果有多组解请输出任意一组无解请输出NO。【输入样例】3 3 1 2 3 2 3 -2 1 3 1【输出样例】5 3 5【算法标签】《洛谷 P5960 差分约束》 #差分约束# #模板题# #Special Judge#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 使用长整型constintN5005,M10005;// 最大顶点数和边数intn,m;// n: 顶点数, m: 边数inth[N],e[M],ne[M],w[M],idx;// 链式前向星存储图intq[N],dist[N];// 队列和距离数组intcnt[N],st[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算法求最短路径并检测负环 * return 存在负环返回false否则返回true */boolspfa(){queueintq;// SPFA队列// 初始化距离为无穷大memset(dist,0x3f,sizeof(dist));dist[0]0;// 超级源点距离为0q.push(0);// 超级源点入队st[0]true;// 标记在队列中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被松弛了n1次说明存在负环if(cnt[j]n1)// 注意是n1因为有超级源点{returnfalse;// 存在负环}// 如果j不在队列中入队if(!st[j]){q.push(j);st[j]true;}}}}returntrue;// 不存在负环}signedmain()// 因为使用了#define int long long{// 输入顶点数和边数cinnm;// 初始化邻接表memset(h,-1,sizeof(h));// 处理m条边while(m--){inta,b,c;cinabc;// 注意这里是 add(b, a, c)不是常见的 add(a, b, c)add(b,a,c);// 添加有向边 b→a权重c}// 添加超级源点到所有顶点的边for(inti1;in;i){add(0,i,0);// 0→i权重0}// 执行SPFA检测是否存在负环if(!spfa()){puts(NO);// 存在负环无解}else{// 输出从超级源点到每个顶点的最短距离for(inti1;in;i){coutdist[i] ;}coutendl;}return0;}【运行结果】3 3 1 2 3 2 3 -2 1 3 1 0 -2 0