首页 > 代码库 > ZOJ 1655 Transport Goods
ZOJ 1655 Transport Goods
最短路问题变形。
题意是说从各个点运送东西到 n;能剩下来最多的。(无向图)
整体变成了求到各点时 最大的 剩余率。
边权变成了过路费率p,0<=p<=1;
存储的时候用 1-p 存 剩余率。实际剩下的货物是 goods *(1-p)
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; int goods[101]; struct lx { int v; double d; }; vector<lx> g[101]; void SPFA(int start) { double dis[101]; bool vis[101]; for(int i=1;i<=n;i++) dis[i]=0,vis[i]=0; dis[start]=1,vis[start]=1; queue<int>q; q.push(start); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int j=0;j<g[u].size();j++) { int v=g[u][j].v; double d=g[u][j].d; if(dis[v]<dis[u]*d) { dis[v]=dis[u]*d; if(!vis[v]) { vis[v]=1; q.push(v); } } } } double ans=0; for(int i=1;i<n;i++) ans+=goods[i]*dis[i]; printf("%.2f\n",ans); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) g[i].clear(); for(int i=1;i<n;i++) scanf("%d",&goods[i]); while(m--) { int u,v; double d; scanf("%d%d%lf",&u,&v,&d); lx now; now.d=(1.0-d); now.v=v,g[u].push_back(now); now.v=u;g[v].push_back(now); } SPFA(n); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。