题目链接：

id=3621">http://poj.org/problem?id=3621

在一个有向图中选一个环，使得环上的点权和除以边权和最大。求这个比值。

经典的分数规划问题，我认为这两篇题解写得非常清楚，能够參考一下http://blog.csdn.net/gengmingrui/article/details/47443705，http://blog.csdn.net/wall_f/article/details/8221807

个人认为01分数规划差点儿都是二分或者迭代比值，从而找到一个最优解，使得原来的函数值等于0

#include<cstdio>

#include<cstring>

#include<queue>

#define eps 1e-3

#define MAXN 1010

using namespace std;

struct T

{

	int v;

	int w;

	int next;

}edge[5005];

int cnt,head[MAXN];

void add_edge(int u,int v,int w)

{

	edge[cnt].v = v;

	edge[cnt].w = w;

	edge[cnt].next = head[u];

	head[u] = cnt++;

}

int n,m;

int w[MAXN];

double dis[MAXN];

bool inque[MAXN];

int vis[MAXN];

bool SPFA(double R)//SPFA推断负权环

{

	queue<int> myque;

	memset(inque,0,sizeof inque);

	memset(vis,0,sizeof vis);

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

		dis[i] = 1e15;

	myque.push(1);

	dis[1] = 0;

	inque[1] = 1;

	vis[1]++;

	while(!myque.empty())

	{

		int u = myque.front();

		myque.pop();

		inque[u] = 0;

		for(int i = head[u]; i != -1; i = edge[i].next)

		{

			int v = edge[i].v;

			int y = edge[i].w;

			if(dis[u] + R*y - w[u] < dis[v])

			{

				dis[v] = dis[u] + R*y - w[u];

				if(!inque[v])

				{

					myque.push(v);

					inque[v] = 1;

					vis[v]++;

					if(vis[v] > n) return 1;

				}

			}

		}

	}

	return 0;

}

int main()

{

	memset(head,-1,sizeof head);

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

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

		scanf("%d",&w[i]);

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

	{

		int a,b,c;

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

		add_edge(a,b,c);

	}

	double l = 0,r = 10000,mid;

	while(r - l > eps)

	{

		mid = (l+r)/2;

		if(SPFA(mid)) l = mid;//因为我们是把权值取反了的。因此题解中的R过大变成了R过小

		else r = mid;

	}

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

	return 0;

}