Poj 1860 Currency Exchange(Bellman-Ford,SPFA解单源最短路径问题)

一、题意

有多个货币交易点，每个只能互换两种货币，兑换的汇率不同，并收取相应的手续费。有N种货币，假定你拥有第S中，数量为V，有M个兑换点。问你能不能通过兑换操作使你最后拥有的S币比起始的时候多。

二、题解

货币的交换是可以重复多次的，所以我们需要找出是否存在正权回路（在这一回路上，顶点的权值能不断增加，即能一直进行松弛），且最后得到的s金额是增加的。说到松弛我们立即会想到Bellman-Ford算法，它的特点是可以处理负权边，并能判断是否存在负环（负权回路）。本题题恰恰与bellman-Ford算法的松弛条件相反，求的是能无限松弛的最大正权路径，但是依然能够利用bellman-Ford的思想去解题。关于bellman-Ford算法请关注本博客对它的详细分析。

bellman-Ford算法的时效性较好，时间复杂度O（VE）。这里也介绍一下它的队列优化算法SPFA。它是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k<<V）。与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。

三、java算法

bellman-Ford算法

import java.util.Scanner;
class Edge{
    int startNode,endNode;
    double exchangeRate;
    double commission;
}
public class Main{
  
 static Edge[] edge=new Edge[210];
 static int pe;
 static int N,M,S;
 static double V;
 static double dis[]=new double[110];
	 
  static boolean bellman_ford(){
	     boolean sign = false;
	     dis[S]=V;
	     for(int j=0;j<N+1;j++){
	         sign=false;
	         for(int i=0;i<pe;i++)
	             if(dis[edge[i].endNode]<(dis[edge[i].startNode]-edge[i].commission)*edge[i].exchangeRate){
	                 dis[edge[i].endNode]=(dis[edge[i].startNode]-edge[i].commission)*edge[i].exchangeRate;
	                 sign=true;
	             }
	         if(!sign)
	             break;
	     }
	     if(sign)
	         return false;
	     else
	         return true;
	 }
	 
  public static void main(String args[]){
	 Scanner sc=new Scanner(System.in);
	 for(int i=0;i<210;i++){
		 edge[i]=new Edge();
	 }
	     N=sc.nextInt();
	     M=sc.nextInt();
	     S=sc.nextInt();
	     V=sc.nextDouble();
         pe=0;
         int a,b;
         double rab,cab,rba,cba;
 
         for(int i=0;i<M;i++){
             a=sc.nextInt();
             b=sc.nextInt();
             rab=sc.nextDouble();
             cab=sc.nextDouble();
             rba=sc.nextDouble();
             cba=sc.nextDouble();
             edge[pe].startNode=a;
             edge[pe].endNode=b;
             edge[pe].exchangeRate=rab;
             edge[pe++].commission=cab;
             edge[pe].startNode=b;
             edge[pe].endNode=a;
             edge[pe].exchangeRate=rba;
             edge[pe++].commission=cba;
         }
         if(bellman_ford())
             System.out.println("NO");
         else
        	 System.out.println("YES");
  } 
}

SFPA算法

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{

 static int MAX_Node =110;
 static int N,M,S;
 static double V;
 static double exchangeRate[][]=new double[MAX_Node][MAX_Node];
 static double commission[][]=new double[MAX_Node][MAX_Node];
 
 public static boolean spfa(int start){
	  Queue<Integer> Que=new LinkedList<Integer>();
	  int cnt[]=new int[MAX_Node];         //记录进入队列的次数，超过N则存在正权回路
	  boolean[] vst=new boolean[MAX_Node]; //记录节点是否在队列中、
	  double[] dis=new double[MAX_Node];  //记录每个结点的最短路径估计值
	  for(int i=0;i<=N;i++){
	       vst[i]=false;
	       cnt[i]=0;
	       dis[i]=0;
	    }
	   dis[start]=V;
	   vst[start]=true;
	   cnt[start]=1;
	   Que.add(start);
	   while(Que.size()!=0){
	    int u=Que.poll();
		vst[u]=false;
		for(int i=1;i<=N;i++){
			if(exchangeRate[u][i]>0 && ((dis[u]-commission[u][i]) * exchangeRate[u][i]) > dis[i]){
		         dis[i]=(dis[u]-commission[u][i]) * exchangeRate[u][i];  //松弛
		         if(!vst[i]){
	                vst[i]=true;
	                Que.add(i);
	                cnt[i]++;
	                if(cnt[i]>=N)
	                   return true;
	             }
		     }
		 }
	  }
	  return dis[S]>V;
	 }
	
  public static void main(String args[]){
	 Scanner sc=new Scanner(System.in);
	     int i;
	     N=sc.nextInt();
	     M=sc.nextInt();
	     S=sc.nextInt();
	     V=sc.nextDouble();
		 for(i=0;i<M;i++){
		    int a,b;
		    a=sc.nextInt();
            b=sc.nextInt();
            exchangeRate[a][b]=sc.nextDouble();
            commission[a][b]=sc.nextDouble();
            exchangeRate[b][a]=sc.nextDouble();
            commission[b][a]=sc.nextDouble();
		  }
		 if(spfa(S))
		         System.out.println("YES");
		     else
		    	 System.out.println("NO");
  } 
}