`
huyifan951124
  • 浏览: 82971 次
社区版块
存档分类
最新评论

Poj1860

 
阅读更多

题目大意:给顶每条边的汇率和所花费的手续费,让你求是否会比原来的钱多。

算法思想:spfa的变形,只需要判断是否存在正环即可,但要注意精度问题,又在这精度上wa了好几次,还是太粗心了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,s,sym;
double v;
int a,b,e;
double ex,ch,ex2,ch2;
bool visited[300];
int head[300],next[300];
double dist[300];
int num[300];
typedef struct Edge
{
    int u;
    int v;
    double cc;
    double ee;
};
Edge edges[300];
void addNode(int u,int v,double cc,double ee)
{
    edges[e].u=u;
    edges[e].v=v;
    edges[e].cc=cc;
    edges[e].ee=ee;
    next[e]=head[u];
    head[u]=e++;
}
bool relax(int u,int v,double cc,double ee)
{
    if(dist[v]<(dist[u]-cc)*ee)
    {
        dist[v]=(dist[u]-cc)*ee;
        return true;
    }
    return false;

}
bool spfa(int src,double value)
{
    memset(num,0,sizeof(num));
    memset(visited,false,sizeof(visited));
    queue<int>que;
    for(int i=1;i<=n;i++)
    {
        dist[i]=0;
    }
    dist[src]=value;
    visited[src]=true;
    que.push(src);
    while(!que.empty())
    {
        int q=que.front();
        que.pop();
        visited[q]=false;

        for(int i=head[q];i+1;i=next[i])
        {
            if(relax(q,edges[i].v,edges[i].cc,edges[i].ee)&&!visited[edges[i].v])
            {
                if(++num[edges[i].v]>n)
                    return false;
                visited[edges[i].v]=true;
                que.push(edges[i].v);
            }
        }
    }

    return true;

}
int main()
{

    scanf("%d%d%d%lf",&n,&s,&sym,&v);
    memset(head,-1,sizeof(head));
    memset(next,-1,sizeof(next));
    e=0;
    for(int i=0;i<s;i++)
    {
        scanf("%d%d%lf%lf%lf%lf",&a,&b,&ex,&ch,&ex2,&ch2);
        addNode(a,b,ch,ex);
        addNode(b,a,ch2,ex2);
    }
    if(!spfa(sym,v))
    {
        printf("YES\n");
    }
    else
        printf("NO\n");
    return 0;
}

 

分享到:
评论

相关推荐

    POJ1860-Currency Exchange【Bellman】

    【标题】"POJ1860-Currency Exchange【Bellman】"是一个编程问题,源自北京大学的在线评测系统POJ(Problem Online Judge),主要考察的是动态规划中的贝尔曼(Bellman)算法。这类问题通常涉及最优化问题的解决,...

    poj题目分类

    * 最短路径算法:例如 Dijkstra、Bellman-Ford、Floyd、Heap+Dijkstra,例如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最小生成树算法:例如 Prim、Kruskal,例如 poj1789、poj2485、poj1258、...

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

    poj训练计划.doc

    - 图的深度优先遍历和广度优先遍历:用于探索图的所有节点,如`poj1860, poj3259`。 - 最短路径算法:如Dijkstra算法和Bellman-Ford算法,用于找到两点间的最短路径,如`poj1062, poj2253`。 - 最小生成树算法:...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    poj各种分类

    包括深度优先遍历(DFS)和广度优先遍历(BFS),用于探索图的所有节点,是解决许多图问题的基础,如poj1860和poj3259所示。 #### 最短路径算法 Dijkstra算法、Bellman-Ford算法和Floyd算法分别适用于无负权边、有...

    POJ题目简单分类(ACM)

    - **最短路径算法**:包括dijkstra、bellman-ford、floyd和heap+dijkstra,如poj1860等,用于找到节点间的最短距离。 - **最小生成树算法**:prim和kruskal算法,如poj1789,用于找到图的最小成本连接。 - **拓扑...

    acm训练计划(poj的题)

    - (poj1860, poj3259, poj1062, poj2253, poj1125, poj2240):介绍迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)、弗洛伊德算法(Floyd)等。 - 使用堆优化的迪杰斯特拉算法。 3. **最小生成树...

    POJ 分类题目 txt文件

    例如,题目poj1860和poj3259就是典型的最短路径问题。 ### 3. 数据结构 数据结构部分包括数组、链表、栈、队列、树、堆、哈希表等,它们在存储和访问数据时提供不同的效率和特性。哈希表(Hash)是一种高效的数据...

    acm poj300题分层训练

    如poj3278、poj2049、poj3083是图遍历的例子,poj1860、poj3259等则是最短路径问题,poj1789、poj2485等则涉及最小生成树。 3. **数据结构**:包括串、排序、简单并查集、哈希表、二分查找、哈夫曼树和堆。poj1035、...

    经典 的POJ 分类

    - POJ 1860、POJ 3259:利用Dijkstra算法解决最短路径问题。 - POJ 1062、POJ 2253:涉及Bellman-Ford算法的应用场景。 - POJ 1125、POJ 2240:Floyd算法的典型实例。 ##### 最小生成树 - **算法**: - Prim...

    acm新手刷题攻略之poj

    ### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...

    ACM-POJ 算法训练指南

    1. **最短路径**:Dijkstra算法、Bellman-Ford算法、Floyd算法等,用于寻找两点间最短路径(poj1860, poj3259, poj1062, poj2253, poj1125, poj2240)。 2. **最小生成树**:Prim算法和Kruskal算法,用于构建图的...

    POJ 分类题目

    - poj1860 - poj3259 - poj1062 - poj2253 - poj1125 - poj2240 - **应用场景**:适用于寻找两点之间的最短路径问题。 **3. 最小生成树算法** - **定义**:包括 Prim 算法和 Kruskal 算法。 - **示例题目**:...

    强大的POJ分类——各类编程简单题及其算法分类

    2. **最短路径算法**:包括Dijkstra、Bellman-Ford、Floyd和堆优化的Dijkstra,如POJ1860、3259、1062、2253、1125和2240。 3. **最小生成树算法**:Prim和Kruskal方法,用于找到图中权重最小的连接所有节点的子树,...

    POJ题目分类

    - **示例题目**: poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **知识点**: - **Dijkstra算法**:适用于带非负权重的有向图和无向图,可以求出图中某一个顶点到其他所有顶点的最短路径。 - **Bellman-...

    ACM常用算法及其相应的练习题.docx

    + poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...

    ACM 详解算法目录

    例如,POJ1860和POJ3259是最短路径算法的典型例题,而POJ1789和POJ2485则是最小生成树算法的经典例题。 数据结构部分涵盖了串、排序、简单并查集、哈希表和二分查找、哈夫曼树、堆和trie树八个方面。例如,POJ1035...

    ACM算法总结大全——超有用!

    1. 图的深度优先遍历(DFS)和广度优先遍历(BFS):用于探索图的所有节点,如poj1860和poj3259。 2. 最短路径算法:包括Dijkstra算法、Bellman-Ford算法、Floyd算法和堆优化的Dijkstra算法,用于寻找图中两点间最短...

Global site tag (gtag.js) - Google Analytics