Bellman_Ford变形求最长路+正权回路或spfa——POJ 1860

2024-09-05 04:18

本文主要是介绍Bellman_Ford变形求最长路+正权回路或spfa——POJ 1860,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对应POJ题目:点击打开链接



Currency Exchange
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 20814 Accepted: 7451

Description

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency. 
For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 - 0.39) * 29.75 = 2963.3975RUR. 
You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B - numbers of currencies it exchanges, and real R AB, C AB, R BA and C BA - exchange rates and commissions when exchanging A to B and B to A respectively. 
Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations. 

Input

The first line of the input contains four numbers: N - the number of currencies, M - the number of exchange points, S - the number of currency Nick has and V - the quantity of currency units he has. The following M lines contain 6 numbers each - the description of the corresponding exchange point - in specified above order. Numbers are separated by one or more spaces. 1<=S<=N<=100, 1<=M<=100, V is real number, 0<=V<=10 3
For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10 -2<=rate<=10 2, 0<=commission<=10 2
Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence. You may assume that ratio of the numeric values of the sums at the end and at the beginning of any simple sequence of the exchange operations will be less than 10 4

Output

If Nick can increase his wealth, output YES, in other case output NO to the output file.

Sample Input

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

Sample Output

YES

Source


题意:有若干种货币,某些币种之间可兑换,给出各种兑换时的汇率r和手续费c,任何兑换都是双向的,但是两个方向的汇率和手续费可能不同,并告知你现在拥有的货币种类s(只拥有一种)及数量v,问是否可以通过货币建兑换最后回到本币种后钱数有所增加。
A->B  (s-c)*r
思路:Bellman_Ford求最长路径,判断是否存在正权回路,是则输出YES,或者spfa求最长路径,用个in[i]数组判断点i入队次数是否大于n, 是则输出YES


Bellman_Ford:


#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
const int MAXN=10000+10;
const int INF=1<<30;
using namespace std;
double dis[105];struct Edge
{int u,v;double r,c;
}E[MAXN];bool Bellman_Ford(int s, int n, double v, int size)
{for(int i=1; i<=n; i++) dis[i]=0.0;dis[s] = v;for(int i=1; i<=n-1; i++){for(int j=0; j<size; j++){if((dis[E[j].u] - E[j].c) * E[j].r > dis[E[j].v])dis[E[j].v] = (dis[E[j].u] - E[j].c) * E[j].r;}}for(int i=0; i<size; i++){if((dis[E[i].u] - E[i].c) * E[i].r > dis[E[i].v])return true;}return false;
}int main()
{//freopen("in.txt","r",stdin);int n,m,s;double v;int size = 0 ;scanf("%d%d%d%lf", &n,&m,&s,&v);for(int i=0; i<m; i++){int u,v;double r,c;scanf("%d%d%lf%lf", &u,&v,&r,&c);E[size].u = u;E[size].v = v;E[size].r = r;E[size++].c = c;scanf("%lf%lf", &r,&c);E[size].u = v;E[size].v = u;E[size].r = r;E[size++].c = c;}bool ok = Bellman_Ford(s,n,v,size);if(ok) printf("YES\n");else printf("NO\n");return 0;
}

spfa:


#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
const int MAXN=10000+10;
const int INF=1<<30;
using namespace std;
double dis[105];
int head[105];
int vis[105];
int in[105];struct Edge
{int v,next;double r,c;
}E[MAXN];bool spfa(int s, int n, double v)
{for(int i=1; i<=n; i++) dis[i] = 0.0;dis[s] = v;queue<int>q;q.push(s);vis[s] = 1;in[s]++;while(!q.empty()){int u=q.front();q.pop();vis[u] = 0;for(int i=head[u]; i!=-1; i=E[i].next){int v = E[i].v;if((dis[u] - E[i].c) * E[i].r > dis[v]){dis[v] = (dis[u] - E[i].c) * E[i].r;if(!vis[v]){vis[v] = 1;in[v]++;if(in[v] > n) return true;q.push(v);}}}if(dis[s] > v) return true;}return false;
}int main()
{//freopen("in.txt","r",stdin);int n,m,s;double v;int size = 0 ;scanf("%d%d%d%lf", &n,&m,&s,&v);memset(head, -1, sizeof(head));for(int i=0; i<m; i++){int u,v;double r,c;scanf("%d%d%lf%lf", &u,&v,&r,&c);E[size].v = v;E[size].r = r;E[size].c = c;E[size].next = head[u];head[u] = size++ ;scanf("%lf%lf", &r,&c);E[size].v = u;E[size].r = r;E[size].c = c;E[size].next = head[v];head[v] = size++;}bool ok = spfa(s,n,v);if(ok) printf("YES\n");else printf("NO\n");return 0;
}


这篇关于Bellman_Ford变形求最长路+正权回路或spfa——POJ 1860的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137922

相关文章

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map

hdu3389(阶梯博弈变形)

题意:有n个盒子,编号1----n,每个盒子内有一些小球(可以为空),选择一个盒子A,将A中的若干个球移到B中,满足条件B  < A;(A+B)%2=1;(A+B)%3=0 这是阶梯博弈的变形。 先介绍下阶梯博弈: 在一个阶梯有若干层,每层上放着一些小球,两名选手轮流选择一层上的若干(不能为0)小球从上往下移动,最后一次移动的胜出(最终状态小球都在地面上) 如上图所示,小球数目依次为

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D