Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

看了网上的代码+《算导》,Java水过

Posted by HeartLC at 2013-04-04 12:21:12 on Problem 1860
import java.util.Scanner;

public class Main
{
       private int n;   //全部有多少种货币
       private int m;   //有多少兑换方法
       private Currency[] currencies;
       private double[] dis;         //解出到了第i种货币时,对应的货币值
       private class Currency
       {
               public int s1;        //货币1
               public int s2;        //货币2
               public double r;     //汇率
               public double c;     //手续费               
               Currency( int s1,int s2,double r,double c )
               {
                         this.s1 = s1;
                         this.s2 = s2;
                         this.r = r;
                         this.c = c;                       
               }     
       }
       
       public void Relax( Currency currency )      //主要是参考《算导》里面的松弛技术
       {
              if( this.dis[currency.s2] < (this.dis[currency.s1]-currency.c)*currency.r )
                  this.dis[currency.s2] = (this.dis[currency.s1]-currency.c)*currency.r;
       }

       public boolean isIncrease()        //主要是参考《算导》里面的Bellman-Ford算法
       {
              for( int i=1;i<=n-1;i++ )
              {
                   for( int j=0;j<2*m;j++ )
                   {
                        this.Relax( this.currencies[j] );
                   }
              }
              for( int i=0;i<2*m;i++ )
              {
                   Currency currency = currencies[i];
                   if( this.dis[currency.s2] < (this.dis[currency.s1]-currency.c)*currency.r )
                        return true;
              }

              return false;
       }

       Main( int n,int m,int s,double v )      //初始化
       {
             this.n = n;
             this.m = m;
             this.currencies = new Currency[2*m];
             this.dis = new double[n+1];
             dis[s] = v;
       }
       public void setM( int i,int s1,int s2,double r12,double c12,double r21,double c21 )       //设置初始值
       {
              this.currencies[i] = new Currency( s1,s2,r12,c12 );
              this.currencies[i+1] = new Currency( s2,s1,r21,c21 );
       }
       public static void main(String[] args)
       {
              Scanner s = new Scanner(System.in);
              int n = s.nextInt();
              int m = s.nextInt();
              int S = s.nextInt();
              double v = s.nextDouble();
              int i=0;
              Main main = new Main( n,m,S,v );
              while( i<2*m )
              {
                     int s1 = s.nextInt();
                     int s2 = s.nextInt();
                     double r12 = s.nextDouble();
                     double c12 = s.nextDouble();
                     double r21 = s.nextDouble();
                     double c21 = s.nextDouble();
                     main.setM( i,s1,s2,r12,c12,r21,c21 );    //设置所有的边
                     i+=2;
               }
               if( main.isIncrease() )
                   System.out.println( "YES" );
               else
                   System.out.println( "NO" );
       }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator