给出一个有向图，每条边有一个权值和时间花费。如果图中无环，输出0，如果有环，找出一个最大的环，最大的意思是环上的权和 / 时间和 最大。
最优比例的题一般二分答案，把题目就变为询问是否存在一个环使得Σcost/Σtime>=k 整理有： Σ(k∗time[v]−cost[v]) <= 0 转换为spfa判负环。
输出路径：记录下返回时那个被加了n次得点，一定是负环里的，记录pre。。。从这个点往前找，出现两次的，加入答案，走到已经出现两次的，说明这个环走回来了。。
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <queue> using namespace std; const int maxn = 60; const double eps = 1e-10; int head[maxn],tot,n,m,u,v; double c,t,tmp; const int maxm = maxn*maxn; struct node{ int v,next; double c,t; }edges[maxm]; void add(int u,int v,double c,double t){ edges[tot].v = v;edges[tot].c = c;edges[tot].t = t;edges[tot].next = head[u];head[u] = tot++; } void init(){ tot = 0 ;memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i = 0 ; i < m ; i++){ scanf("%d%d%lf%lf",&u,&v,&c,&t); add(u,v,c,t); } } bool inq[maxn]; double dis[maxn]; int num[maxn],pre[maxn]; int spfa(double mid){ queue<int>q; for(int i = 1;i <= n;i++){ q.push(i); inq[i] = true; num[i] = 0; dis[i] = 0.0; } while(!q.empty()){ int tmp = q.front();q.pop(); inq[tmp] = false; for(int k = head[tmp];k != -1;k = edges[k].next){ if(dis[edges[k].v] > eps+dis[tmp]+edges[k].t*mid-edges[k].c){ dis[edges[k].v] = dis[tmp]+edges[k].t*mid-edges[k].c; pre[edges[k].v] = tmp; if(!inq[edges[k].v]){ inq[edges[k].v] = true; q.push(edges[k].v); num[edges[k].v]++; if(num[edges[k].v] > n-1) return edges[k].v; } } } } return 0; } void sov(){ double L = 0,R = 1e10; while(fabs(R - L) > eps){ double mid = (L+R)/2; if(spfa(mid)){ tmp = mid; L = mid; } else R = mid; } } int cnt[maxn],ans[maxn]; void print(){ int u = spfa(tmp); if(u == 0){ printf("0\n");return ; } int tt = 0; memset(cnt,0,sizeof(cnt)); while(cnt[u] <= 1){ cnt[u]++; if(cnt[u] == 2) ans[tt++] = u; u = pre[u]; } printf("%d\n",tt); for(int i = tt-1; i >= 0 ; i--){ printf("%d%c",ans[i],i == 0?'\n':' '); } } int main(){ init(); sov(); print(); }