csp201809-4
2023-04-18 15:27:02 时间
这是一道差分约束求最长路的图的问题:
通过已知的条件可以容易列出以下不等式:
2*a1<=x1+x2<=2*a1+1
3*a2<=x1+x2+x3<=3*a2+2
3*a3<=x2+x3+x4<=3*a3+2
.......
3*an-1<=xn-2+xn-1+xn<=3*an-1+2
2*an<=xn-1+xn<=2*an+1
以及xn>=1
我们可以通过一些简单的移项将其变成:
xi+xk>=num1 ; -xi-xk>=-num2
或者
xi+xj+xk>=num1 ; -(xi+xj+xk)>=-num2
可以定义Sj=x0+x1+....xj,那么就可以转换为:
Sj-Si>=num的状态,其几何含义为从i点到j点的长度最小为num
想要求得x的最小值,那么就需要求得num的最大值,由此转换为求图的最长路的问题,鉴于其存在负权路,那么使用SPFA最好。
#include<bits/stdc++.h> using namespace std; int a[305]; int dis[305]; int vis[305]; vector<pair<int,int>>G[305]; int n; void SPFA(){//存在负权求最长路 for(int i=0;i<=n;i++){dis[i]=0,vis[i]=0;} vis[0]=1; queue<int> p; p.push(0); while(!p.empty()){ int now=p.front();p.pop(); for(int i=0;i<G[now].size();i++){ if(dis[G[now][i].first]<dis[now]+G[now][i].second){ dis[G[now][i].first]=dis[now]+G[now][i].second; if(vis[G[now][i].first]!=1){ p.push(G[now][i].first); } } } vis[now]=0; } } int main(){ cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=0;i<=n;i++){ G[0].push_back({i,0});//超级源点 } for(int i=0;i<n;i++){ G[i].push_back({i+1,1});//x大于0 } G[0].push_back({2,2*a[1]}); G[2].push_back({0,-2*a[1]-1}); G[n-2].push_back({n,2*a[n]}); G[n].push_back({n-2,-2*a[n]-1}); for(int i=2;i<=n-1;i++){ G[i-2].push_back({i+1,3*a[i]}); G[i+1].push_back({i-2,-3*a[i]-2}); } SPFA(); for(int i=1;i<=n;i++){ cout<<dis[i]-dis[i-1]<<" "; } }
超级源点的使用是防止图不连通,其另一个作用是初始化最长路为0。
那么Sj就是超级源点到j点的最长路dis[j]了,求出xj的方法就是Sj-Sj-1=dis[j]-dis[j-1]
代码AC
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击