Description：

一个无向图，点有权值，边有代价，找一个回路，可以重复经过点，权值不累加，可以多次经过边，代价累加，最小化 $\sum权值/\sum代价$ 。

$1\le n \le 1000,1\le m \le 5000$

Solution：

$01$ 分数规划，可以发现最终路径一定没有环套环的情况，也就是说边只经过一次，权值和代价不在一起，那就把边的权值设为终点的权值，反正最终一定是回路，然后 $01$ 分数规划，设当前二分的值为 $mid$ ，然后把所有边的边权都设为 $v-mid\times c$ ，然后用 $SPFA$ 判断是否存在负环

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

double val[MAXN];

#define MAXM 5010

struct edge

{

	int to,nxt;

	double v,c;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,double c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].c = c;e[edgenum].v = val[b];e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

bool vis[MAXN];

double dis[MAXN];

bool negcir;

void dfs(int k,double x)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		double c = e[i].v - x * e[i].c;

		if(dis[e[i].to] >= dis[k] + c)continue;

		if(vis[e[i].to]){negcir = true;return;}

		dis[e[i].to] = dis[k] + c;

		dfs(e[i].to,x);

		if(negcir)return;

	}

	vis[k] = false;

}

bool check(double x)

{

	for(int i = 1;i <= n;++i)vis[i] = dis[i] = 0;

	negcir = false;

	for(int i = 1;i <= n;++i)

	{

		dfs(i,x);

		if(negcir)return true;

	}

	return false;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%lf",&val[i]);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,(double)c);

	}

	double l = 0,r = 1000000000,mid;

	while(r - l > 1e-6)

	{

		mid = (l + r) / 2;

		if(check(mid))l = mid;

		else r = mid;

	}

	printf("%.2lf\n",l);

	return 0; 

}