3220 - 最小圈

4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3

3.66666667

提示

 【样例说明】 

<span style="font-family:宋体;">样例</span><span>1</span><span style="font-family:宋体;">中共有</span><span>2</span><span style="font-family:宋体;">个圈</span><span>(1,2,3)</span><span style="font-family:宋体;">和</span><span>(1,2,4)</span><span style="font-family:宋体;">。其中第一个圈的平均值为</span><span>5</span><span style="font-family:宋体;">，第二个圈的平均值为</span><span>11/3</span><span style="font-family:宋体;">。样例</span><span>2</span><span style="font-family:宋体;">中存在一个负圈。</span><span></span>



<span style="font-family:宋体;">【数据范围及约定】</span><span></span>



<span>20%</span><span style="font-family:宋体;">的数据：</span><span>n&lt;=100,m&lt;=1000</span><span style="font-family:宋体;">；</span><span></span>



<span>50%</span><span style="font-family:宋体;">的数据：</span><span>n&lt;=1000,m&lt;=5000</span><span style="font-family:宋体;">；</span><span></span>



<span>100%</span><span style="font-family:宋体;">的数据：</span><span>n&lt;=3000,m&lt;=10000</span><span style="font-family:宋体;">；</span><span></span>



<span>100%</span><span style="font-family:宋体;">的数据：</span><span>|w[i,j]|&lt;=10^7</span><span style="font-family:宋体;">。</span><span></span>

C++解答

/*
	author	:hzoi_ztx
	title	:最小圈 
	ALG		:01分数规划  SPFA判负环 
	comment	:
	2014 10 08 test
*/

#include <cstdio>
#include <cstring>

#define	maxn	3010
#define	maxm	10010
#define	info	4500.0
#define	accu	0.000000001

struct FST{
	int to , next ;
	double len ;
} map[maxm] ; int star[maxn] = {0} , tot = 0 ;
void addEdge(const int u , const int v , const double w) {
	tot ++ ; map[tot].to = v ; map[tot].len = w ;
	map[tot].next = star[u] ; star[u] = tot ;
}



int n , m ;
int u , v , p ;
double L = -info , R = info , ans , tmp ;

bool exist[maxn] ;
int len[maxn] ;//记录最短路的长度，当其大于n时存在负环 
double dis[maxn] ; 

int line[maxn+10] , head = 1 , tail = 0 ;
inline int F(const int x) { return ((x-1)%n)+1 ; }
inline int front() { return line[F(head)] ; }
inline int back() { return line[F(tail)] ; }
inline void push_head(const int x) { line[F(--head)] = x ; }
inline void push_back(const int x) { line[F(++tail)] = x ; }
inline void pop_head() { head ++ ; }
inline bool empty() { return head>tail ; }

bool spfa(double ans) {
	memset(exist , 1 , sizeof (exist)) ;
	memset(len , 0 , sizeof (len)) ;
	memset(dis , 0 , sizeof (dis)) ;
	for (u = 1 ; u <= n ; u ++ ) push_back(u) ;
	while (!empty()) {
		u = front() ; pop_head() ; exist[u] = false ;
		p = star[u] ;
		while (p) {
			v = map[p].to ;
			tmp = map[p].len-ans ;
			if (dis[u]+tmp < dis[v]) {
				dis[v] = dis[u]+tmp ;
				len[v] = len[u] +1 ;
				if (len[v] > n) return true ;
				else if (!exist[v]) {
					exist[v] = true ;
					if (dis[v] < dis[front()]) push_head(v) ;
					else push_back(v) ;
				}
			}
			p = map[p].next ;
		}
	}
	return false ;
}

void Bsearch() {
	while (R-L >= accu) {
		ans = L+(R-L)/2 ;
		if (spfa(ans)) R = ans ;
		else L = ans ;
	}
}

int main() {
	//#define  READ
	#ifdef   READ
		freopen("cycle.in" ,"r",stdin ) ;
		freopen("cycle.out","w",stdout) ;
	#endif
	scanf("%d%d", &n , &m ) ;
	for (int i = 1 ; i <= m ; i ++ ) {
		scanf("%d%d%lf", &u , &v , &tmp) ;
		addEdge(u , v , tmp) ;
	}
	Bsearch() ;
	printf("%.8lf\n", ans ) ;
	return 0 ;
}