学步园

大意：求一个环，求一个解集x 使得 valuex/Tx 的值最大！

思路：求一个最优比率正环，首先我们要明确知道，题目的数据保证一定存在环，而且最优的解一定是一个环，不存在环套环的情况。那怎么去求解正环呢？我目前不知道有啥有效算法，所以我把原数据取反，把原问题转换成判断图是否存在负环，而判断负环很容易，用SPFA就OK。那有负环代表着什么呢？我们以权值 -value[i] + mid*T[i]（已经取反）连的边存在负环说明mid的值小了，需要增加，反之，需要减少。我们在一定的范围内去解方程，即 Q(L) = Valuex - L* x Tx这个方程，其中x代表一个子集域，x[i]只能取0,1.
求得的Q(L)其实无关紧要，最重要的是二分枚举枚举的mid值，而且要保证比率一定在我们枚举的范围之内，mid的最终值才是我们的答案。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

const int MAXN = 1010;
const int MAXM = 5010;
const int INF = 0x3f3f3f3f;
const double eps = 1e-3;

struct Edge
{
	int v, next;
	double w;
}edge[MAXM];

int n, m;
int cnt;

int first[MAXN];
double d[MAXN];
int value[MAXN];

void init()
{
	cnt = 0;
	memset(first, -1, sizeof(first));
}

void read_graph(int u, int v, double w)
{
	edge[cnt].v = v, edge[cnt].w = w;
	edge[cnt].next = first[u], first[u] = cnt++;
}

int spfa(int src, double mid)
{
	queue<int> q;
	bool inq[MAXN] = {0};
	int count[MAXN] = {0};
	for(int i = 1; i <= n; i++) d[i] = (i == src)? 0:INF;
	q.push(src);
	while(!q.empty())
	{
		int x = q.front(); q.pop();
		inq[x] = 0;
		for(int e = first[x]; e != -1; e = edge[e].next)
		{
			int v = edge[e].v;
			double w = -value[v] + mid*edge[e].w;
			if(d[v] > d[x] + w)
			{
				d[v] = d[x] + w;
				if(!inq[v])
				{
					inq[v] = 1;
					if(++count[v] > n) return 0;
					q.push(v);
				}
			}
		}
	}
	return 1;
}

void read_case()
{
	init();
	for(int i = 1; i <= n; i++) scanf("%d", &value[i]);
	while(m--)
	{
		int u, v;
		double w;
		scanf("%d%d%lf", &u, &v, &w);
		read_graph(u, v, w);
	}
}

void solve()
{
	double x = 0, y = 100;
	while(y-x > eps)
	{
		double mid = x+(y-x)/2.0;
		if(spfa(1, mid))
		{
			y = mid;
		}
		else
		{
			x = mid;
		}
	}
	printf("%.2lf\n", x);
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		read_case();
		solve();
	}
	return 0;
}