【POJ3621】Sightseeing Cows 分数规划
规划 分数 cows
2023-09-11 14:15:27 时间
【POJ3621】Sightseeing Cows
题意:在给定的一个图上寻找一个环路,使得总欢乐值(经过的点权值之和)/ 总时间(经过的边权值之和)最大。
题解:显然是分数规划,二分答案ans,将每条边的权值变成(ans*边权-2*起始点点权),然后我们希望找出一个环,使得环上的总边权<0
(一开始我把题意理解错了,题中给的是单向边,我把它当成是双向边+每条边只能走一次了~,想出一堆做法都接连pass掉)
然后就直接用SPFA判负环就好了嘛!由于原图不一定联通,所以一开始就把所有点都入队就完事了
#include <cstdio> #include <iostream> #include <queue> #include <cstring> using namespace std; int n,m,cnt; int f[1010],to[10010],next[10010],head[1010]; int pa[5010],pb[5010],pt[5010],len[1010],inq[1010]; double dis[1010],val[10010]; queue<int> q; void add(int a,int b,double c) { to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++; } int solve(double sta) { memset(head,-1,sizeof(head)); memset(len,0,sizeof(len)); cnt=0; int i,u; for(i=1;i<=m;i++) add(pa[i],pb[i],sta*pt[i]-f[pa[i]]); while(!q.empty()) q.pop(); for(i=1;i<=n;i++) q.push(i),dis[i]=0.0,len[i]=1; while(!q.empty()) { u=q.front(),q.pop(),inq[u]=0; for(i=head[u];i!=-1;i=next[i]) { if(dis[to[i]]>dis[u]+val[i]+1e-4) { dis[to[i]]=dis[u]+val[i]; len[to[i]]=len[u]+1; if(len[to[i]]>n) return 1; if(!inq[to[i]]) { inq[to[i]]=1; q.push(to[i]); } } } } return 0; } int main() { scanf("%d%d",&n,&m); int i,a,b,c; double l=0.0,r=0.0,mid; for(i=1;i<=n;i++) scanf("%d",&f[i]),r=max(r,1.0*f[i]); for(i=1;i<=m;i++) scanf("%d%d%d",&pa[i],&pb[i],&pt[i]); while(r-l>1e-4) { mid=(l+r)*0.5; if(solve(mid)) l=mid; else r=mid; } printf("%.2f",l); return 0; }
相关文章
- 算法洗脑系列(8篇)——第七篇 动态规划
- [usaco]3.4.4 变形的动态规划问题Electric Fence
- LeetCode-801. 使序列递增的最小交换次数【动态规划,滚动数组】
- LeetCode-357. 统计各位数字都不同的数字个数【排列组合,递归,动态规划】
- Leetcode2100: 适合打劫银行的日子(medium, 滑动窗,动态规划)
- 杭州地铁规划五年规划,2017-2022
- leetcode 377. 组合总和 Ⅳ----动态规划之双重for循环变式----求排列数
- Atiti。流量提升软件设计大纲规划 v1 q45
- Atitit。sql2016标准化的规划方案 v3 q2a
- 基于遗传算法在机器人路径规划中的应用研究(Matlab代码实现)
- 基于Dijkstra和A*算法的机器人路径规划(Matlab代码实现)
- 基于SA模拟退火优化的TWVRP路径规划matlab仿真
- 基于Qlearning强化学习的机器人路线规划仿真
- elasticsearch容量规划
- 网络安全自学入门:(超详细)从入门到精通学习路线&规划,学完即可就业
- 基于模型预测(MPC)的四轮转向车辆轨迹规划(Matlab代码实现)
- 【运维规划、管理、体系建设】一位女运维的自述:三年为公司节省十亿元现金,我们怎么做到的