[洛谷春令营 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!”(不含引号)。

输入输出样例

输入样例#1:

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

输出样例#1:

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(N3) 的 Floyd 从 dis[stp - 1][][] 推出 dis[stp][][]。

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

Code: O(N4) [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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai