[洛谷春令营 D7T3] 最小密度路径【分步Floyd】
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; }
发表评论