PS:此題數組名皆引用：戳我
? ? ? ?題目大意：有n個點m條有向邊的圖，邊上有花費，點上有收益，點可以多次經過，但是收益不疊加，邊也可以多次經過，但是費用疊加。求一個環使得收益和/花費和最大，輸出這個比值。
? ? ? ?顯然這就是經典的分數規劃題啊，就是最優比率環，那么就二分答案，將所有邊（u，v）的邊權改為【v的點權-（u，v）原邊權*mid】（因為d[i]=a[i]-L*b[i]），然后判一下是否有正環，有的話就說明有更優的答案（F(L)=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])>0即sigma(a[i]*x[i])/sigma(b[i]*x[i])>L），縮小范圍繼續二分。判正環有夠別扭的，那就全部改成相反數然后判負環吧233333
代碼如下：
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<queue> using namespace std; struct zs{int too,pre;double dis;}e[10001]; struct poi{int pos;double dis;}; priority_queue<poi>q; bool operator <(poi a,poi b){return a.dis-b.dis>1e-3;} int n,m,x,y,now,tot,num[1001],last[1001]; bool v[1001]; double l,r,mid,dis[1001],fun[1001]; bool spfa(int x) {for(int i=1;i<=n;i++)dis[i]=23333333;v[x]=true;q.push((poi){1,0});dis[1]=0;while(!q.empty()){int i,too;for(i=last[now=q.top().pos],too=e[i].too,q.pop();i;i=e[i].pre,too=e[i].too){double dist=e[i].dis*mid-fun[too];if(dis[too]-dis[now]-dist>1e-3){dis[too]=dis[now]+dist;if(!v[too])v[too]=1,q.push((poi){too,e[i].dis}),num[too]++;if(num[too]>233)return 1;}}v[now]=0;}return 0; } int main() {scanf("%d %d",&n,&m);for(int i=1;i<=n;i++)scanf("%lf",&fun[i]);for(int i=1;i<=m;i++){scanf("%d %d %lf",&x,&y,&e[++tot].dis);e[tot].too=y;e[tot].pre=last[x];last[x]=tot;}l=0;r=10000;while(r-l>1e-3){memset(v,0,sizeof(v));memset(num,0,sizeof(num));mid=(l+r)/2;if(spfa(1))l=mid;else r=mid;}printf("%.2lf",l); }
?
)
