首页 > 代码库 > Zoj 1655 Transport Goods 最短路的应用

Zoj 1655 Transport Goods 最短路的应用

2024-07-12 06:05:32   221人阅读

这道题目真是充分显示了窝的智商低下，首先题目在有中文翻译的情况下看了半天没看懂，= =

然后已知这题的分类是最短路了还是不会做，= =

一开始想着在dij扩展的的时候就把最大运送值算好，不过后来发现正向运输和反向运输的值显然是不相等的o(╯□╰)o

后来直接把每个城市作为起点dij了，反正n就一百，n^3就n^3了，后来发现可以从多条路一起送到终点

无奈看了题解，发现原来dij算的应该是终点到各个点的最小费率（最大比率），这样不仅正向反向算结果是一样的，而且不会漏。

话说题目本来就是要把每个城市里面的物品全部运送到终点的，只是对于每个城市选一条费率最小的边而已，这不是裸的dij么，这都不会，sad...

PS：这题有重边，WA哭TAT

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int INF = INT_MAX / 4;const int maxn = 105;int vis[maxn],n,m,w[maxn];double p[maxn][maxn],d[maxn];void dijkstra() {    memset(vis,0,sizeof(vis));    for(int i = 1;i <= n;i++) {        d[i] = -1;    }    d[n] = 1;    for(int k = 1;k <= n;k++) {        double maxv = -1; int x = n;        for(int i = 1;i <= n;i++) if(!vis[i] && d[i] > maxv) {            maxv = d[x = i];        }        vis[x] = true;        for(int i = 1;i <= n;i++) if(!vis[i] && p[x][i] >= 0) {            if(d[i] == -1) d[i] = d[x] * p[x][i];            else d[i] = max(d[i],d[x] * p[x][i]);        }    }}int main() {    while(scanf("%d%d",&n,&m) != EOF) {        for(int i = 1;i < n;i++) {            scanf("%d",&w[i]);        }        for(int i = 1;i <= n;i++) {            for(int j = 1;j <= n;j++) {                p[i][j] = -5;            }        }        for(int i = 1;i <= m;i++) {            int a,b;            double c; scanf("%d%d%lf",&a,&b,&c);            p[a][b] = p[b][a] = max((1 - c),p[a][b]);        }        dijkstra();        double ans = 0;        for(int i = 1;i < n;i++) if(d[i] > 0) {            ans += d[i] * w[i];        }        printf("%.2f\n",ans);    }    return 0;}

　　


联系
我们