[洛谷春令营 D7T3] 最小密度路径【分步Floyd】

• 2018-02-21
• 0
• 0

Problem:

题目描述

给出一张有N个点M条边的加权有向无环图，接下来有Q个询问，每个询问包括2个节点X和Y，要求算出从X到Y的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。

输入输出格式

输入格式：

第一行包括2个整数N和M。

以下M行，每行三个数字A、B、W，表示从A到B有一条权值为W的有向边。

再下一行有一个整数Q。

以下Q行，每行一个询问X和Y，如题意所述。

输出格式：

对于每个询问输出一行，表示该询问的最小密度路径的密度（保留3位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。

输入输出样例

3 3
1 3 5
2 1 6
2 3 6
2
1 3
2 3

5.000
5.500

说明

1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000

Solution:

本题是一道思路非常 喵 妙的最短路题。

我们用 dis[stp][i][j] 表示 i -> j 走恰好 stp 步的最短路径长度。

那么可以 O(N) 枚举 stp，跑一次 O(N³) 的 Floyd 从 dis[stp - 1][][] 推出 dis[stp][][]。

然后在 dis[][A][B] 中找出密度最小的答案输出即可，也可以预处理。

Code: O(N⁴) [2753K, 56MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define DINF 1e10
using namespace std;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int N, M, dis[52][52][52], Q;
double minden[52][52];

int main(){
	getint(N), getint(M);
	memset(dis, 0x3f, sizeof(dis));
	for(register int i = 1; i <= M; i++){
		int A, B, W;
		getint(A), getint(B), getint(W);
		if(W < dis[1][A][B]) dis[1][A][B] = W;
	}
	for(register int stp = 2; stp < N; stp++)
		for(register int k = 1; k <= N; k++)
			for(register int i = 1; i <= N; i++)
				for(register int j = 1; j <= N; j++)
					dis[stp][i][j] = min(dis[stp][i][j], dis[stp - 1][i][k] + dis[1][k][j]);  // 分步 Floyd 算法 
	memset(minden, 0x43, sizeof(minden));  // memset 为 double 赋极大值 
	for(register int i = 1; i <= N; i++)
		for(register int j = 1; j <= N; j++)
			for(register int stp = 1; stp < N; stp++)
				if(dis[stp][i][j] < INF)
					minden[i][j] = min(minden[i][j], (double)dis[stp][i][j] / stp);
	getint(Q);
	while(Q--){
		int X, Y;
		getint(X), getint(Y);
		if(minden[X][Y] < DINF) printf("%.3f\n", minden[X][Y]);
		else puts("OMG!");
	}
	return 0;
}