学步园

相关题解参见这里，这一类问题这里都讲到了，很全面。

/*
 * poj3621 AC 625ms
 * 所谓的01分数规划+spfa判断正(负)环+二分枚举答案
 * 	   为什么就那么慢，那个pascal的0ms是直接打印的答案吧，快得逆天了啊！
 * 经常会纠结这种问题：
 * 	   对一个任务选择一种方案，存在不同的价值与成本，要求(价值/成本)最大的方案。
 *     
 *     事实上这都是 运筹学 的关于规划的内容，所以要去看书了。
 * 	   
 * 	   除开规划部分，spfa判断正(负)环时要注意图可能并不连通，所以要枚举每一个点作为起点，
 * 同时用vis[]记录已经访问过的点，避免重复计算，类似问题之前也遇到过。
 * */
#include<stdio.h>
#include<memory.h>
#include<queue>
#include<cmath>
#define INF 1000000000
using namespace std;

int n,p,f[1005];
struct EDGE
{
	int v,t,next;
}edge[5005];
int head[1005],tot,num[1005];
double d[1005];

inline void init()
{
//	FILE* fin;
//	fin = fopen("d.in","r");
	scanf("%d%d",&n,&p);
//	fscanf(fin,"%d%d",&n,&p);
	int i,j,k,m;
	memset(f,0,sizeof(f));
	for(i=1;i<=n;i++)
		scanf("%d",&f[i]);
//		fscanf(fin,"%d",&f[i]);
	tot = 0;
	memset(edge,0,sizeof(edge));
	memset(head,0,sizeof(head));
	for(i=1;i<=p;i++)
	{
		scanf("%d%d%d",&j,&k,&m);
//		fscanf(fin,"%d%d%d",&j,&k,&m);
		edge[++tot].v = k;
		edge[tot].t = m;
		edge[tot].next = head[j];
		head[j] = tot;
	}
//	fclose(fin);
	return;
}

inline bool spfa(double l)
{
	int i,j,k;
	bool inq[1005],vis[1005];
	double w;
	memset(vis,false,sizeof(vis));
	
	queue<int> q;
	for(j=1;j<=n;j++)			//注意，可能存在离散的点。	
	{
		if(vis[j]) continue;	//访问过的点就跳过。
		memset(num,0,sizeof(num));
		memset(inq,false,sizeof(inq));
		memset(d,0,sizeof(d));
		d[j] = 0,q.push(j),inq[j] = true,num[j] = 1;
		while(!q.empty())
		{
			k = q.front();
			q.pop();
			inq[k] = false,vis[k] = true;
			for(i=head[k];i;i=edge[i].next)
			{
				w = f[k]-l*edge[i].t;		//将点权移到边权上，为什么可以对应？
				if(d[edge[i].v]<d[k]+w)		//是判断是否有正环
				{
					d[edge[i].v] = d[k]+w;
					if(!inq[edge[i].v])
					{
						num[edge[i].v]++;
						if(num[edge[i].v]>n) return true;	//有正环
						q.push(edge[i].v);
						inq[edge[i].v] = true;
					}
				}
			}
		}
	}
	return false;	//无正环
}

inline void solve()
{
	double mid,l,r,Eps = 0.000001;
	l = 0,r = 5000;
	do
	{
		mid = (l+r)/2;			//F(L) = a[i]-mid*b[i] mid即为答案，函数为减函数。
		if(spfa(mid)) 
			l = mid;			//有正环，则答案需要增大，移动下界。
		else r = mid;			//无正环，则答案需要减小，移动上界。
	}while(abs(r-l)>Eps);
	if(l>Eps) printf("%.2f\n",l); else printf("0\n");
}

	
int main()
{
	init();
	solve();	
	return 0;
}