当前位置:编程学习 > C/C++ >>

HDU OJ 4318 Power transmission [最短路spfa]

题意:有一个发电站 s ,将电传送至  t , 有 许多路线可以走,每走 一条路 有损失,求埙失的最小值。
思路:(1)转化为 最短路问题,损失 = max- max*(1-a%)*(1-b%)……*(1-%n)(假设任意一条路线);
             (2)求的 (1-a%)*(1-b%)……*(1-%n)的最大值 即可。
             (3)现在 使 a 代替 1-a%,b 代替 1-b%……;即求 a*b*c*……*n的最大值!(注意::0<a<1……);
             (4)现在以e为底  取对数log a*b……*n 即log a +( log b)……+(log n) 有函数性质可知,log a 为 负值……log n 为负值。
              (5)求 【log a】+ log【b】+…………+【logn】 的最小值 即可(【】代表绝对值)这就成了 最短路了!!
AC代码:
[cpp]
#include<stdio.h> 
#include<string.h> 
#include<math.h> 
#include<queue> 
#include<vector> 
using namespace std; 
int s,t,Max,ac[50005]; 
double d[50005]; 
struct node 

    int x; 
    double y; 
}; 
vector<node> V[50005]; 
void spfa(int n) 

    int a,b,i,j; 
    for(a=1;a<=n;a++) 
    { 
        ac[a]=0; 
        d[a]=999999999; 
    } 
    d[s]=0; 
    queue<int> Q; 
    Q.push(s); 
    ac[s]=1; 
    while(!Q.empty()) 
    { 
        i= Q.front(); 
        //printf("i----%d\n",i); 
        Q.pop(); 
        ac[i]=0; 
        for(a=0;a<V[i].size();a++) 
        { 
            j=V[i][a].x; 
            if(d[j]>d[i]+V[i][a].y) 
            { 
                d[j]=d[i]+V[i][a].y; 
                if(ac[j]==0) 
                { 
                    Q.push(j); 
                    ac[j]=1; 
                } 
            } 
        } 
    } 
    if(d[t]<999999999) 
    { 
        printf("%.2lf\n",(1-exp(-d[t]))*Max); 
    } 
    else 
        printf("IMPOSSIBLE!\n"); 
    for(a=1;a<=n;a++) 
        V[a].clear(); 
} www.zzzyk.com
int main() 

    int a,b,n,m,i,j; 
    while(~scanf("%d",&n)) 
    { 
        for(a=1;a<=n;a++) 
        { 
            scanf("%d",&m); 
            while(m--) 
            { 
                scanf("%d%d",&i,&j); 
                double k; 
                k=-log(1-double(j)/100); 
                node t1={i,k}; 
                V[a].push_back(t1); 
            } 
        } 
        scanf("%d%d%d",&s,&t,&Max); 
        spfa(n); 
    } 


 

作者:PIAOYI0208
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,