正題

題目鏈接:https://www.luogu.org/problemnew/show/P1768

---

題目大意

求一條回路使得路上$\frac{\sum v_i}{\sum p_i}$最大。

---

解題思路

考慮01分數(shù)規(guī)劃
$$\frac{\sum v_i}{\sum p_i}=ans$$
$$\sum v_i=ans?\sum p_i$$
轉為二分判定
$$\sum v_i?ans?\sum p_i>0$$
$$ans?\sum p_i?\sum v_i<0$$

然后對于每次二分，計算邊權，然后求負環(huán)

---

$code$

#include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=7100,M=21000; struct node{int to,next;double v,p,w; }a[M*2]; queue<int> q; double f[N]; int n,m,tot,ls[N],cnt[N]; double l,r; bool v[N]; void addl(int x,int y,double v,double p) {a[++tot].to=y;a[tot].next=ls[x];a[tot].v=v;a[tot].p=p;ls[x]=tot; } bool spfa() {for(int i=1;i<=n;i++)f[i]=2147483647/3;memset(cnt,0,sizeof(cnt));q.push(n);cnt[n]=1;f[n]=0;v[n]=1;while(!q.empty()){int x=q.front();v[x]=0;q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;cnt[y]=cnt[x]+1;if(cnt[y]>=n&&a[i].w<0)return true;if(!v[y]){v[y]=1;q.push(y);}}} }return false; } bool check(double ans){for(int i=1;i<=tot;i++)a[i].w=a[i].p*ans-a[i].v;if(spfa()) return true;else return false; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;double v,p;scanf("%d%d%lf%lf",&x,&y,&v,&p);addl(x,y,v,p);}n++;for(int i=1;i<n;i++)addl(n,i,0,0);l=0;r=500;while(r-l>1e-2){double mid=(l+r)/2;if(check(mid)) l=mid;else r=mid;}if(l==0) printf("-1");else printf("%.1lf",l); }

總結

以上是生活随笔為你收集整理的P1768-天路【负环,SPFA,01分数规划,二分答案】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。