计蒜客题库

计蒜客题库题解系列:最小边权路径

题目测试地址:https://nanti.jisuanke.com/t/10418

题意:

已知一个包含 n 个顶点 m 条边的有向图,每条边包含一个权值 z。定义顶点 u 到顶点 v 的某一条路径(路径中至少包含一条边)的平均边权为该路径上所有边的权值之和除以边的数量得到的商。顶点 u 到顶点 v 的最短平均边权路径为顶点 u 到顶点 v 的所有路径中平均边权最小的路径。求该有向图中任意两点之间的最短平均边权路径。

解法:

这题是一道比较有意思的题目,刚开始读懂题目以后,你可能会有点疑惑,如果出现环的话会怎么样。这是这题的重点,求极限,如果在某个环里面一直绕是最优的,那么最后整个平均权值的极限会趋向于这个环的平均值。  用dp[i][j][k] 表示 i 到 j 经过 k 条路径的最小值。

转移类似于 floyd , 转移如下

注意 k 要放在最外层枚举。如果最优路径上不出现环,那么 k < n ,如果最优路径上出现了环,可以证明只会出现一个环,我们可以枚举进入这个环是哪个点。所以我们可以写出 的复杂度的算法。  具体可以看下面代码


#include 
#include 
#include 

using namespace std;

const int mmax = 110;
int cost[mmax][mmax][mmax];
double C[mmax];
bool G[mmax][mmax];
int main() {
    int n, m;
    while (cin >> n >> m) {
        memset(cost, 0x3f, sizeof cost);
        int inf = cost[0][0][0];
        for (int i = 0; i < m; ++i) {
            int x, y, z;
            cin >> x >> y >> z;
            --x, --y;
            cost[x][y][1] = min(cost[x][y][1], z);
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 1; k < n; ++k) {
                    for (int e = 0; e < n; ++e) {
                        if (cost[i][j][k] < inf && cost[j][e][1] < inf) {
                            cost[i][e][k + 1] = min(cost[i][e][k + 1], cost[i][j][k] + cost[j][e][1]);
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            C[i] = 1e20;
            for (int j = 1; j <= n; ++j) {
                if (cost[i][i][j] < inf) {
                    C[i] = min(C[i], 1.0 * cost[i][i][j] / j);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                G[i][j] = 0;
                for (int k = 1; k <= n; ++k) {
                    if (cost[i][j][k] < inf) {
                        G[i][j] = 1;
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                double ans = 1e20;
                for (int k = 1; k <= n; ++k) {
                    if (cost[i][j][k] < inf) {
                        ans = min(ans, 1.0 * cost[i][j][k] / k);
                    }
                }
                for (int k = 0; k < n; ++k) {
                    if (G[i][k] && G[k][j] && C[i]) {
                        ans = min(ans, C[k]);
                    }
                }
                if (!G[i][j]) {
                    printf("NO");
                } else {
                    printf("%.3lf", ans);
                }
                printf("%c", j == n - 1? '\n':' ');
            }
        }
    }

    return 0;
}

1 comment

评论

你的邮箱地址并不会被公开显示 Required fields are marked *

你可以使用 HTML 标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>