Dayi Lin, Ph.D.

Principal Researcher, AI & Software Engineering

POJ-1860 解题报告

POJ

题意简述

某城市有M(1<=M<=100)个货币兑换站,可以兑换N(1<=N<=100)种货币,每个兑换站只能互换两种货币,且汇率与手续费各不相同。某人初始时手中有V元货币S,问他是否有可能通过货币兑换,在最后换回货币S时实现盈利,有可能则输出YES,否则输出NO。

算法分析

本题可抽象为一张有N个节点的有向图,一个兑换站就是它所兑换的两种货币间的两条有向边。边的权值有两个:汇率及手续费。

问题可化简为:从定点出发找正权环。由于可以通过无限次走正权环使得收益趋于无穷,所以不考虑返程开销。

容易发现,这是Bellman-Ford算法的逆用。将求最短路改为求最长路,再找可以无限松弛的正环,即可得解。

只要将Bellman-Ford稍微改进。初始时所有节点不再赋为无穷大,而是改为无穷小(0)。比较时,注意权值计算式的变化即可。详见程序样例。

具体的Bellman-Ford及最短路各算法另开文。

Problem Status: AC。时间32ms,内存184k

程序样例

#include<stdio.h>

struct edge {
  int a;
  int b;
  double r;
  double c;
};

int bellman_ford(double d[], struct edge x[], int n, int m, int s, double v) {
  int i, j, flag;
  d[s] = v;
  for (i = 1; i <= n - 1; i++) {
    flag = 0;
    for (j = 0; j < 2 * m; j++) {
      if (d[x[j].b] < (d[x[j].a] - x[j].c) * x[j].r) {
        d[x[j].b] = (d[x[j].a] - x[j].c) * x[j].r;
        flag = 1;
      }
    }
    if (!flag) break;
  }
  for (j = 0; j < 2 * m; j++) {
    if (d[x[j].b] < (d[x[j].a] - x[j].c) * x[j].r) return 1;
  }
  return 0;
}

int main() {
  int n, m, s, i, t = 0;
  struct edge x[202];
  double v, d[101] = {
    0
  };
  scanf("%d%d%d%lf", & n, & m, & s, & v);
  for (i = 0; i < m; i++) {
    scanf("%d%d%lf%lf", &
      x[t].a, & x[t].b, & x[t].r, & x[t].c);
    t++;
    x[t].a = x[t - 1].b;
    x[t].b = x[t - 1].a;
    scanf("%lf%lf", & x[t].r, & x[t].c);
    t++;
  }
  if (bellman_ford(d, x, n, m, s, v)) printf("YES\n");
  else printf("NO\n");
  return 0;
}

1 Comments on “POJ-1860 解题报告”

  1. Pingback: POJ-2240 解题报告 | #Hello World!

Leave a Reply

Your email address will not be published. Required fields are marked *