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