Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
看了网上的代码+《算导》,Java水过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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator