游客 注册 | 登录
中文 | En

3220 - 最小圈

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

考虑带圈的有向图G=(V，E)以及w:E→R，每条边e=(i，j)(i<>j,i∈V)的权值定义为w[i,j]，令n=|V|。C=(c1,c2,…,ck)(ci∈V)是G中的一个圈当且仅当(c[i],c[i+1])(1<=i<k)和(c[k],c[1])都在E中，这是称k为圈c的长度同时令c[k+1]=c[1]，并定义圈c=(c1,c2,…,ck)的平均值为，即c上所有边的权值的平均值。令为G中所有圈c的平均值的最小值。现在的目标是：在给定了一个图G=(V，E）以及w：E→R之后，请求出G中所有圈c的平均值的最小值

题目输入

第一行包含两个整数n和m，并用一个空格隔开，其中n=|V|，m=|E|分别表示途中有n个点和m条边。接下来m行，每行包含用空格隔开的三个数i，j和w[i,j]，表示有一条边(i,j)且该边的权值为w[i,j]。输入数据保证图G=(V,E)连通，存在圈且有一个点能到达其他所有点。

题目输出

仅包含一个实数，要求输出到小数点后8位。

输入/输出样例

输入格式

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

输出格式

3.66666667

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 ;
}
请先登陆