P1576 最小花费 题解

CSDN同步

原题链接

前置知识:

最短路。( exttt{SPFA,dijkstra}) 会一个即可解决本题。

简要题意:

已知若干组关系 (x,y,z),即 (x)(y) 两人转账需要扣除 (z \%) 的手续费(吞钱),问 (A)(B) 打钱,至少要打多少,才能保证 (B) 得到 (100) 元。

这时代吞钱的人越来越多了。

  • 建图: 给 (x)(y) 连边,边权为 (1-frac{z}{100}),表示 (t) 元钱从这条边流过,就只剩下 ((1-frac{z}{100}) imes t),其余的被吞了

  • 方法:用最短路算法求出从 (A)(B) 的最大汇率。

  • 累积方案:汇率是乘法不是加法,和传统最短路有所不同。

  • 最短路:本人用了 ( exttt{SPFA}).(反正卡到 (O(n^2)) 我也不怕,(n leq 2000) 就是这么弱)

时间复杂度:(O(n^2)).(( exttt{SPFA}) 的时间复杂度就是这么玄学)

实际得分:(100pts).

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=2e3+1;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int n,m,s,t; bool vis[N];
vector<pair<int,double> >G[N];
double ans=1e9,dis[N];

inline double min(double a,double b) {
	return a<b?a:b;
}

inline void SPFA() {
	queue<int>q; q.push(s);
	dis[s]=1; vis[s]=1; //准备宽搜
	while(!q.empty()) {
		int u=q.front(); q.pop();
		vis[u]=0; //每个节点入队多次,所以
		for(int i=0;i<G[u].size();i++) { //枚举转移
			int v=G[u][i].first;
			if(dis[u]*G[u][i].second>dis[v]) {
				dis[v]=dis[u]*G[u][i].second; //把钱吞掉
				if(!vis[v]) { //维护哈希
					vis[v]=1; q.push(v);
				}
			}
		}
	}
}

int main(){
//	freopen("money.in","r",stdin);
//	freopen("money.out","w",stdout);
	n=read(),m=read();
//	for(int i=1;i<=n;i++) dis[i]=0;
	while(m--) {
		int x=read(),y=read();
		double z; cin>>z;
		G[y].push_back(make_pair(x,1-z/100));
		G[x].push_back(make_pair(y,1-z/100));
	} s=read(),t=read(); SPFA(); //建图,跑最短路
	cout<<fixed<<setprecision(8)<<100/dis[t]<<endl; 
	return 0;
}

原文地址:https://www.cnblogs.com/bifanwen/p/12631872.html