| ||||||||||
| 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