学步园

就是一个最优比率环噻，，二份答案+SPFA()得解，，最优比率请参见类似物：http://blog.csdn.net/loriex/article/details/18980625

妥妥的AC代码：

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
#define min(a,b) a<b?a:b
#define MAX 51
#define inf 1000000000
#define eps 0.0001
class cycle{
	public:
		int n;
		int graph[MAX][MAX];
		double map[MAX][MAX];
		bool ROAD[MAX][MAX];
		void make(double l){
			for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				map[i][j] = graph[i][j] - l;
		}
		bool SPFA(){//若存在负环，，ans为true,否则ans为false
			int vis[n+1];
			bool in[n+1]; 
			double dist[n+1];
			queue<int> Q;
			for (int i = 1; i <= n; i++){
				in[i] = vis[i] = 1;
				dist[i] = 0;
				Q.push(i);
			}
			while(!Q.empty()){
				int s = Q.front(); Q.pop();
				in[s] = false;
				vis[s]++;
				if ( vis[s] > n+5 ){
					return true;
				}
				for (int i = 1; i <= n; i++)
					if ( ROAD[s][i] && dist[i] > dist[s]+map[s][i] ){
						dist[i] = dist[s] + map[s][i];
						if ( !in[i] ){
							in[i] = true;
							Q.push(i);
						}
				}
			}
			return false;
		}
	public:
		void nul(){
			memset(ROAD,0,sizeof(ROAD));
			memset(graph,0,sizeof(graph));
		}
		void init(){
			int m,a,b,l;
			scanf("%d%d",&n,&m);
			for (int i = 1; i <= m; i++){
				scanf("%d%d%d",&a,&b,&l);
				graph[a][b] = ROAD[a][b]?min(graph[a][b],l):l;
				ROAD[a][b] = true;
			}
		}
		double work(){
			double l = 0,r = inf;
			while(r-l >= eps){
				double mid = (r+l)/2;
				make(mid);
				bool x = SPFA();
				if ( x == true )	r = mid;
				else 				l = mid;
			}
			return r;
		}
};
cycle Q;
int main(){
	int T; 
	scanf("%d",&T);
	for (int i = 1; i <= T; i++){
		printf("Case #%d: ",i);
		Q.nul();
		Q.init();
		double an = Q.work();
		if ( an < inf )
			printf("%.2lf\n",an);
		else 
			printf("No cycle found.\n");
	}
	return 0;
}