ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2207 Consistet Unit System

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2207


解法


ワーシャルフロイド法で解くことができます。

この問題では単位の関係が云々といっていますが、これはグラフに落として考えることができます。
(例)1 km = 10^3 m の場合
・km というノードから m というノードまで 10^3 のコストで到達することができる。
・逆に m から km まで 10^-3 のコストで到達することができる。

上の例のような感じでグラフに落としてやります。

そして矛盾が生じないということは単位の変換をして、元の単位に戻してもその値が変わらないということになります。
⇒ あるノードをAとすると、AからAに到達するまでの最短経路が0になる。


ソースコード

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;

#define REP(i,x,n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)

static const int INF = (1 << 29);

int N;
int dp[200][200];
map<string, int> id;

int convert(string s){
  int res = 0;
  bool minus = false;
  
  if(s[0] == '-') minus = true;
  
  rep(i,s.size()){
    if(minus && i == 0) continue;
    res = 10 * res + (s[i] - '0');
  }
  
  if(minus) res = -res;

  return res;
}

int main(){
  while(cin >> N && N){
    rep(i,200) rep(j,200) dp[i][j] = INF;
    id.clear();

    int count = 0;
    
    rep(i,N){
      string a,b,x;
      char tmp1,tmp2;
      cin >> tmp1 >> a >> tmp2 >> x >> b;
      
      if(id.find(a) == id.end()) id[a] = count++;
      if(id.find(b) == id.end()) id[b] = count++;
     
      int A,B,X;
      A = id[a];
      B = id[b];
      X = convert(x.substr(3));
      
      dp[A][B] =  X;
      dp[B][A] = -X;
    }
    
    rep(k,count) rep(i,count) rep(j,count){
      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
    }
    
    bool ok = true;
    rep(i,count) if(dp[i][i] != 0) ok = false;

    cout << (ok ? "Yes" : "No") << endl;
  }
  return 0;
}