P1768 天路

題意：

小X為所有的路徑定義了兩個值，Vi和Pi，分別表示火車線路的風景趣味度和乘坐一次的價格。現在小X想知道，乘客從任意一個景點開始坐火車走過的一條回路上所有的V之和與P之和的比值的最大值。以便為顧客們推薦一條環繞旅游路線（路線不一定包含所有的景點，但是不可以存在重復的火車路線）。

題解：

01分數規劃+spfa判負環
spfa判斷負環要用DFS，因為BFS版本會超時
因為圖不一定了連通，所以最好每個點都跑一遍

代碼：

#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<algorithm> using namespace std; #define N 10005 #define db double const double inf=201*1.0; #define M 500005 const double eps=1e-4; db d[N]; bool vis[N]; int f[N],num[N],top=1,head[N]; int n,m,s,cnt=1; struct Node{int v;db val,dis;int next; }node[200100]; inline void add(int u,int v,db dis,db val) {node[++top].v=v;node[top].val=val;node[top].dis=dis;node[top].next=head[u];head[u]=top; } bool spfa(db mid,int u)//dfs-spfa判環 {vis[u]=1;for(int i=head[u];i;i=node[i].next){int k=node[i].v;db val=node[i].val;double dis=node[i].dis;if(d[k]>d[u]+mid*val-dis){d[k]=d[u]+mid*val-dis;if(vis[k]||spfa(mid,k)) return true;}}vis[u]=0;return false; } bool check(db mid) //判斷答案是否合理 {for(int i=1;i<=n;i++){d[i]=1e9;vis[i]=false;}for(int i=1;i<=n;i++){if(spfa(mid,i)==true) return true;}return false; } int main() {cin>>n>>m; for(int i=1;i<=m;i++) //按題意建圖{ int u,r;db p,k;scanf("%d%d%lf%lf",&u,&r,&p,&k);add(u,r,p,k);}db l=0,r=inf;while(r-l>eps)//二分答案，eps為取精度 {db mid=(l+r)/2;if(check(mid)==true) l=mid;else r=mid;}if(!l) puts("-1");else printf("%.1lf",l); return 0; }

總結

以上是生活随笔為你收集整理的P1768 天路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。