【AcWing单源最短路建图】1126. 最小花费

Myth丶恋晨 2024-04-01 16:52 71阅读 0赞

[1126. 最小花费 - AcWing题库][1126. _ - AcWing]

题意：

![6f10e27db651447fa600ccd302251d58.png][]

思路：

边权积模型，取对数转化为单源最短路问题

设刚开始的钱是x,每两个人之间的交易率  
则100=x∗(w1∗w2∗w3..)  
要想x最小，就要求w1∗w2∗w3..最大  
即求log(w1∗w2∗w3..)=log(w1)+log(w2)+..log(w1∗w2∗w3..)=log(w1)+log(w2)+..最大，  
因为w都是小于1的，所以log(w)都是小于0的，所以将每个数取相反数，  
问题转化成求**取反后的最小值**，即转换成最短路问题

**扩展：对于一般的边权积问题，若边权大于１，则可以通过最短路求边权积最小；若边权积小于１，则可以通过最短路求边权积最大**

**总结：**

**图论最重要的是怎么建图**

**建图时：**

**１.先考虑结点的含义**

**２.考虑边权的含义，边权的含义大多数时候为题目要求的东西，如果发现不合适就要改变边权值，然后再去跑跑看**

**考虑完怎么建图后只需打板子就行了**

在这道题中，结点的含义就是扣除手续费之后剩下来的钱

边权的含义就是扣除一定的手续费，数值是百分比

细节：

因为是求积，因此dist数组不必为0x3f3f3f3f，dis\[s\]应为1

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e3+10,mxe=1e5+10,mnf=0x3f3f3f3f;
    struct ty{
        int to,next;
        double w;
    }edge[mxe<<1];
    queue<int> q;
    int n,m,x,y,w,tot=0,s,t;
    int head[mxn],vis[mxn];
    double dis[mxn];
    void add(int u,int v,double w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            vis[i]=0;
        }
        while(!q.empty()) q.pop();
    }
    double spfa(int u,int v){
        dis[u]=1;
        q.push(u);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]<dis[u]*(edge[i].w)){
                    dis[edge[i].to]=dis[u]*(edge[i].w);
                    if(!vis[edge[i].to]){
                        vis[edge[i].to]=1;
                        q.push(edge[i].to);
                    }
                }
            }
        }
        return dis[t];
    }
    int main(){
        //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&w);
            add(x,y,1.0-1.0*w/100);
            add(y,x,1.0-1.0*w/100);
        }
        scanf("%d%d",&s,&t);
        printf("%.8f\n",100/spfa(s,t));
    }

[1126. _ - AcWing]: https://www.acwing.com/problem/content/1128/
[6f10e27db651447fa600ccd302251d58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/2d04ab30a6b341908f2f43e29ecdd90c.png