ZOJ-1655 Transport Goods---dijkstra变形&&最长路-白红宇

ZOJ-1655 Transport Goods---dijkstra变形&&最长路

阅读量：6878 次

发布时间：2019-06-26

本文共 1867 字，大约阅读时间需要 6 分钟。

题目链接：

题目大意：

有N-1个城市给首都(第N个城市)支援物资，有M条路，走每条路要耗费一定百分比的物资。问给定N-1个城市将要提供的物资，和每条路的消耗百分比。求能送到首都的最多的物资数量

思路：

由于每条路有费用率，比如1-2路的费用率是0.2，2-3的费用率是0.3，那么x质量的物品经1-3只剩下x*(1-0.2)*(1-0.3)，一开始弄错了，以为消耗的是X*0.2*0.3，用最短路求，这显然是错误的，因为在路上消耗的不能算成费用率的乘积，比如之前的例子，在路上消耗的应该是x*0.2 + x*(1-0.8)*0.3,而直接计算剩余的，就可以用乘积的形式x*(1-0.2)*(1-0.3),所以直接将Map存为剩余率（1-费用率），而且数据中存在重边，所以要保存剩余率最大的那条边，然后用dijkstra求最长路，最长的话也是可dijkstra最短路思想一样，只是找出离源点的最短点变成离源点的最长点，更新dist时也是往大的更新，dist初始化时应该初始化成0。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              10 #include
              
               11 #define MEM(a, b) memset(a, b, sizeof(a));12 using namespace std;13 typedef long long ll;14 const int maxn = 100 + 10;15 const int INF = 0x3f3f3f3f;16 int T, n, m, cases, tot;17 int w[maxn];18 double Map[maxn][maxn];19 double d[maxn];//d[i]表示从源点到i的最大剩余率，由于是无向图，所以也是i到源点的最大剩余率20 bool v[maxn];21 void dijkstra(int u)22 {23 for(int i = 0; i <= n; i++)d[i] = 0;//初始化成最小的24 d[u] = 1;25 memset(v, 0, sizeof(v));26 for(int i = 0; i < n; i++)27 {28 int x;29 double m = 0;//这里是double！！！因为这个点一直WA30 for(int i = 1; i <= n; i++)if(!v[i] && d[i] - m > 1e-8)m = d[x = i];//这里改成找最大值31 v[x] = 1;32 for(int i = 1; i <= n; i++)33 {34 if(!v[i] && Map[x][i] >= 0)d[i] = max(d[i], d[x] * Map[x][i]);//松弛操作变成更新为最大值35 }36 }37 }38 int main()39 {40 while(cin >> n >> m)41 {42 for(int i = 1; i < n; i++)cin >> w[i];43 for(int i = 1; i <= n; i++)44 for(int j = 1; j <= n; j++)Map[i][j] = 0;45 int u, v;46 double c;47 while(m--)48 {49 cin >> u >> v >> c;50 Map[u][v] = Map[v][u] = max(1.0 - c, Map[u][v]);//有重边！！！51 }52 dijkstra(n);53 double ans = 0;54 for(int i = 1; i < n; i++)55 {56 ans = ans + 1.0 * w[i] * d[i];57 }58 printf("%.2f\n", ans);59 }60 return 0;61 }

转载于:https://www.cnblogs.com/fzl194/p/8735534.html

你可能感兴趣的文章