不懂01分数规划的可以先看大佬博客~ 传送门
01分数规划，即给定模型求sum(ai)/sum(bi)的最值；
我们可以改变一下式子的形态：
sum(ai)/sum(bi)>=L
=sum(ai)-L*sum(bi)>=0
所以我们可以通过二分判断L的取值；
最重要的还是要构造一个具有单调性的式子使得可以二分求解
看题啦~
小澳的葫芦
题目描述
葫芦世界有n个葫芦，标号为 1−n。n个葫芦由m条藤连接，每条藤连接了两个葫芦，这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在1号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他想沿着藤爬到n号葫芦上，其中每个葫芦只经过一次。
小澳找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。
输入
输入第一行两个正整数 n,m，分别表示葫芦的个数和藤数。
接下来m行，每行三个正整数 u,v,w，描述一条藤，表示这条藤由u连向v，小澳爬过这条藤需要消耗w点能量。
输出
一行一个实数，表示答案（误差不超过 10^-3）。
样例输入 Copy
4 6
1 2 1
2 4 6
1 3 2
3 4 4
2 3 3
1 4 8
样例输出 Copy
2.000
提示
对于所有数据，小澳爬过每条藤消耗的能量不会超过 10^3，且一定存在一条从1到n的路径。
题意：
给出n个点m条边的有向无环图，求1~n的最短路径的权值之和与所经过点个数的最小比值。
思路：
这里借鉴一下01分数规划的思想，我们设答案为x，可以推出
对于一条经过k边的路径有 （w1+w2+w3+……+wk）/k >=x;
即 w1+w2+w3+……+wk >= k*x
我们把x拆开后移到左边 (w1-x)+(w2-x)+(w3-x)+…+(wk-x)>=0
满足单调性~
还有一点就是需要
另建一个起点0，连接一条0到1长度为0的边，就此将问题转化为长度和边数最小比值。这个问题的求解需要分数规划。
于是就得到了这样一个算法：
二分答案x，每次将每一条边的权值减去x求最短路，判断1~n的最短路是否大于0：若大于0，则说明答案ans>x；否则说明ans<x。
代码：要注意距离和权值的存储必须使用double类型
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define I_int ll #define inf 0x3f3f3f3f inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=1e6+7; const double eps=1e-12; double w[maxn]; int h[maxn],e[maxn],ne[maxn],idx;//邻接表存图 double d[maxn];//保存最短距离 bool st[maxn];//判断是否已经确定最短路 int n,m; void add(int a,int b,int c){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool check(double x){ for(int i=0;i<idx;i++) w[i]-=x;//根据构造出来的式子来进行二分检验 for(int i=1;i<=n;i++) d[i]=1e9+7,st[i]=0; d[0]=0;queue<int>q;q.push(0);st[0]=1; //SPFA while(q.size()){ int t=q.front(); q.pop(); st[t]=0; for(int i=h[t];~i;i=ne[i]){ int j=e[i]; if(d[j]>d[t]+w[i]){ d[j]=d[t]+w[i]; if(!st[j]){ q.push(j); st[j]=1; } } } } for(int i=0;i<idx;i++) w[i]+=x;//恢复原状 return d[n]-eps<0; } void AC(){ n=read();m=read(); memset(h,-1,sizeof h); int u, v,w; add(0,1,0); for(int i=1;i<=m;i++){ u=read();v=read();w=read(); //cin>>u>>v>>w; add(u,v,w); } double l=0,r=maxn,res; //求最小值 //while(r-l>eps) while(l+eps<r){ double mid=(l+r)/2.0; if(check(mid)) res=mid,r=mid;//满足题意，还可以更小，区间左移 else l=mid;//不满足题意，区间右移 } printf("%.3lf",res); } int main(){ AC(); return 0; }
接近自闭，还有个Graph在补
参考资料：
