[文章目录]
Description
给出一张n个点，m条边有向图，每个点有点权，边有边权，求一个起点终点相同的路径使得路径上的
点权/ 边权*该边走的次数最大。输出这个比值。
n<=1000,m<=5000
一见到比值最大化直接想01分数规划。
设想这个路径的样子：显然路径上至少存在一个环。假设存在多个环，我们发现其中任意一个都可以单选。
假想有两个环，一个比值大，另一个比值小。他们合起来的比值肯定小于其中大的哪一个环。加上走重点或边代价变大，收益不变的情况，显然答案对应的路径肯定能只用一个环表示。
那么问题就变成了求一个最优比率环。回归到分数规划，将函数归为边权上，那么只要有一个正权环就说明解能够更优。
spfa判正权环。求最长路径，如果有一个点入队了超过n次，说明就存在正权环。跑一次的极限复杂度为O(n*m)，实际上为O(跑得过)。
图论有坑啊，待填啊。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,f[1100],num[1100];
int head[1100],nxt[5100],to[5100],cnt,data[5100];
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
}
double dis[1100];
queue<int>q;
bool v[1100];
bool check(double k)
{
for(int i=1;i<=n;i++) dis[i]=-1000000000;
memset(v,0,sizeof(v)); memset(num,0,sizeof(num));
while(!q.empty()) q.pop();
q.push(1); v[1]=1; dis[1]=0;
int x,y;
while(!q.empty())
{
x=q.front(); q.pop(); v[x]=0;
for(int i=head[x];i;i=nxt[i])
if(dis[y=to[i]]<dis[x]+f[to[i]]-k*data[i])
{
dis[y]=dis[x]+f[y]-k*data[i];
if(!v[y]) q.push(y),num[y]++,v[y]=1;
if(num[y]>n) return true;
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&f[i]);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
double l=0,r=10000.0,mid;
while(r-l>1e-4)
{
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.2lf\n",l);
return 0;
}