【floyed】【HDU1217】【Arbitrage】-白红宇

【floyed】【HDU1217】【Arbitrage】

阅读量：6981 次

发布时间：2019-06-27

本文共 1124 字，大约阅读时间需要 3 分钟。

题目大意：

给你几种货币，以及几种汇率关系，问是否存在套利的可能？

思路：

初步想法：图上存在一个环的路径上权值相乘大于1....

~~再者：该如何找到图上所有环呢....~~

好吧经过鸟神和况神的指点,,~~,这题就是一道floyed求最小环而已（权重取负）（虽然差不多，其实还是差挺远..）~~

对于乘法处理转换为ln...Orz一下鸟神

~~Floyed求最小环（后来才发现没关系）~~

一开始天真的以为.....只要求一遍Floyed 再判断一下F[i][i]就好，但要记住这个图是带负权值的....所以可能是走过几圈的........

（但其实这个题没有影响，只需要判断最终的结果是否小于0即可，多走几圈，依旧会小于0。。事实上也A了..)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #define oo 0x13131313using namespace std;const double e=2.718281828459;const int maxn=31;double F[maxn][maxn];map
              
                money;int n,m; //number of pricevoid Clear(){ for(int i=0;i
               
                >a; money[a]=i; } scanf("%d",&m); for(int i=1;i<=m;i++) { cin>>a>>c>>b; c=-log(c); F[money[a]][money[b]]=c; }}void init(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout);}int main(){ // init(); int Case=0; while(cin>>n&&n) { Case++; printf("Case %d: ",Case); Clear(); input(); solve(); if(ans<0) printf("Yes\n"); else printf("No\n"); }}

即时这个题不需要。

但还是要搞懂怎么求最小环！！未完待续..。

带负权求不出

转载于:https://www.cnblogs.com/zy691357966/p/5480362.html

你可能感兴趣的文章