Bellman-Fordアルゴリズム-POJ 1806-JAVA言語記述


POJ1806 
Bellman‐Fordアルゴリズムの逆利用.
初期両替の通貨をソースポイントとして見てbellman-fordを用いて解くことができ,要求が実現できれば図面に無限に増大できるループが存在することを説明し,これはbellman-fordアルゴリズムによりループが求められているかどうかを判断することができ,解く過程で元の通貨に両替され,以前より多くのお金があることが発見されれば,直接アルゴリズムを終了することができる.両替中に各通貨の値が負でない必要があるため、すべての初期パスの長さを0に設定し、両替に従ってエッジを緩和することができます.
上のコード:
import java.util.Arrays;
import java.util.Scanner;

/*
 *    :        ,  Rab,           Cab 。。。。。。。        (   -    ) *   ,
 *                 ,   value          ,        。

                ,           ,         ,    a b  b a       
     ,       。。。。。

   :
3 2 1 20.0                         //            ,      ,      
1 2 1.00 1.00 1.00 1.00            // a,  b, rab, cab, rba, cba
2 3 1.10 1.00 1.10 1.00				//rab    	cab   
   :
YES
 * 
 * 
 * */
public class POJ1806 {
	static int n; //     
	static int m; //      
	static int s; //     s    
	static double v; //   s      
	static Edge[] rate;
	static Edge[] commissino;
	static double[] value;
	public static final double EPS = 1E-8;// 10   -8   

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		s = sc.nextInt() - 1;//    1                 0
		v = sc.nextDouble();
		int a;
		int b;
		double rab;
		double cab;
		double rba;
		double cba;
		rate = new Edge[m * 2];
		commissino = new Edge[m * 2];
		value = new double[n];

		for (int i = 0; i < 2 * m; i++) {
			a = sc.nextInt() - 1;
			b = sc.nextInt() - 1;
			rab = sc.nextDouble();
			cab = sc.nextDouble();
			rba = sc.nextDouble();
			cba = sc.nextDouble();

			rate[i] = new Edge();
			rate[i].s = a;//   a
			rate[i].e = b;
			rate[i].v = rab;
			commissino[i] = new Edge();
			commissino[i].s = a;
			commissino[i].e = b;
			commissino[i].v = cab;

			i++;
			rate[i] = new Edge();
			rate[i].s = b;//             b
			rate[i].e = a;//
			rate[i].v = rba;
			commissino[i] = new Edge();
			commissino[i].s = b;//
			commissino[i].e = a;//
			commissino[i].v = cba;
		}
		new POJ1806().solve();
	}

	public void solve() {
		if (bellman_ford(s, rate, commissino)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}

	private static boolean bellman_ford(int ss, Edge[] rat, Edge[] com) {
		// TODO Auto-generated method stub
		Arrays.fill(value, 0);//    value        0
		value[ss] = v;
		boolean released;
		while (value[ss] <= v + EPS) {
			released = false;
			for (int i = 0; i < 2 * m; i++) {
				if (value[rat[i].e] + EPS < (value[rat[i].s] - com[i].v) * rat[i].v) {//      Bellman_Ford            
					value[rat[i].e] = (value[rat[i].s] - com[i].v) * rat[i].v;
					released = true;
					//System.out.println(Arrays.toString(value));
				}
			}
			if (!released) {
				//System.out.println(true);
				return value[ss] > v + EPS;
			}
		}
		//System.out.println(value[s]);
		return true;
	}

}

class Edge {
	int s;
	int e;
	double v;
}