Currency Exchange poj1860
个人认为这是一道比较好的题目，考虑了很多知识点。很显然题目是要求一种兑换方案使最后的钱最多，但如果我们将钱数都取其相反数，那么反过来就是求最小的钱数了（当然此时的钱数是个负数了，不过为了叙述方便，我们就暂且认定钱可以为负吧）。到了这里还存在一个问题，在已知的一种兑换方案中一旦存在负环，那么该方案就不存在最小钱数了，因为它可以无限小，则该方案肯定满足题意。所以该题在求出最短路径后，应该还要判断是否存在负环，而且负环应至少有一个顶点在某一种兑换方案所在的路径上，即此题还要求出一个包含s点的连通子图。
PS：此题作为单源最短路径的题目，因为起点和终点是同一个点，所以此处我将起点拆成了两个点。
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
struct
{
int a,b;
double r,c;
}map;
double d;
vector<int>map1;//邻接表
bool visit;
int n,m,s;
double v;
bool relax(int u,int v,double r,double c)
{
if((d+c)*r<d)
{
d=(d+c)*r;
return true;
}
return false;
}
//此处是为了求出与s连通的点，用visit数组标记是否连通
void dfs(int u)
{
visit=true;
for(int i=0;i<map1.size();i++)
if(!visit])
dfs(map1);
}
int main()
{
int i,j,a,b;
while(~scanf("%d%d%d%lf",&n,&m,&s,&v))
{
for(i=1;i<=n+1;i++)
map1.clear();
i=0;
while(m--)
{
scanf("%d%d",&a,&b);
map.a=a;map.b=b;
if(map.b==s)
map.b=n+1;
scanf("%lf%lf",&map.r,&map.c);
map1.a].push_back(map.b);
i++;
map.a=b;map.b=a;
if(map.b==s)
map.b=n+1;
scanf("%lf%lf",&map.r,&map.c);
map1.a].push_back(map.b);
i++;
}
m=i;
for(i=1;i<=n+1;i++)
d=100000000.0;
d=-v;
for(i=1;i<n;i++)
for(j=0;j<m;j++)
relax(map.a,map.b,map.r,map.c);
if(-d>v)
{
printf("YES\n");
continue;
}
for(i=1;i<=n+1;i++)
visit=false;
//此处判断负环，若有负环，则肯定可以满足，当然要保证负环中有至少一个顶点在dfs求得的子连通图中
dfs(s);
for(j=0;j<m;j++)
if((visit.a]||visit.b])&&relax(map.a,map.b,map.r,map.c))
{
printf("YES\n");
break;
}
if(j==m)
printf("NO\n");
}
return 0;
}
页:
[1]