首页 > 代码库 > zoj1655 最短路变形

zoj1655 最短路变形

2024-07-16 14:26:34   218人阅读

题意：HERO过的首都需要货物，需要从其他的城市吧货物送到首都，每条道路都会需要消耗一定比例的货物，问最多能送多少货物到首都。

思路：如果每个点的比例是1，到达首都的比例就是经过的路径的（1-消耗比）的乘积，反正是无向的，所以可以反过来推，首都的货物比是1，而到达每座

城市的货物就是所经过的路径（1-消耗比）的乘积，则由此可见，我们可以求首都到任意城市的最大比值；最后把每个点的最大比值乘以每个点的货物加起来

即是结果。

 

#include<stdio.h>#include<string.h>const int maxn = 150;const double lep = 1e-8;double map[maxn][maxn];int vis[maxn];double dis[maxn];int w[maxn];int n,m;void init(){    memset(vis,0,sizeof(vis));    memset(dis,0,sizeof(dis));    for(int i=0;i<=n;i++)    {        for(int j =0;j<=n;j++)            map[i][j] = -1;    }}double  DIJ() // 求每座城市送物资的最大比值；{    int i,j;    int u = n;    dis[u] = 1;    vis[u] = 1;    for(i=1;i<=n;i++)    {        for(j=1;j<n;j++)        {            if(!vis[j] && dis[j] < dis[u] * map[u][j])            {                dis[j] = dis[u] * map[u][j];            }        }        double max  = 0;        for(j=1;j<n;j++)        {            if(!vis[j] && dis[j] - max > lep)            {                max = dis[j];                u = j;            }        }        vis[u] =1;    }    double ans = 0;    for(i= 1; i<n;i++)        ans += w[i] * dis[i];    return ans;}int main(){    int i;    while(~scanf("%d%d",&n,&m))    {        init();        for(i=1;i<n;i++)            scanf("%d",&w[i]);        w[n]= 0;        for(i=0;i<m;i++)        {            int a,b;            double c;            scanf("%d%d%lf",&a,&b,&c);            if(map[a][b] < (1 - c) )            {                map[a][b] = map[b][a] = 1-c;        //        printf("%lf\n",map[a][b]);            }        }        printf("%.2lf\n",DIJ());    }    return 0;}/*5 6101010101 3 01 4 02 3 02 4 03 5 04 5 0*/

 


联系
我们