《算法竞赛·快冲300题》每日一题：“单位转换”

《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。

“ 单位转换” ，链接： http://oj.ecustacm.cn/problem.php?id=2136

题目描述

【题目描述】 给定 n 组单位换算关系式，q 组询问，每次将某个单位转换成另一个单位。
   单位换算关系式：1 = 。表示左边的 1 个单位的 等价于 个单位的 。
   询问格式： to 。询问 个单位的 等价于多少个单位的 。
【输入格式】 输入第一行为正整数 n,q。1≤n≤100,1≤q≤10000。
   接下来 n 行，每行均为：1 <unitA> = <value> <unitB>。
   接下来 q 行，每行均为： <unitA> to <unitB>。
   其中<value>为浮点数 v，属于区间 [0.001,1000]，小数点后最多 9 位数字。
   <unitA>，<unitB>最多包含 20 个小写字母。
   查询中的单位保证至少在一个单位转换等式中有定义。每个单位最多只能以一种方式转换为其他任何单位。
【输出格式】 对于每个查询，输出所请求单位的值，如果无法回答查询，则输出“impossible”。
   输出结果与标准答案绝对误差或者相对误差不超过 10-6 被视为正确。
【输入样例】

样例1：
4 3
1 foot = 12 inch
1 yard = 3 foot
1 meter = 100 centimeter
1 centimeter = 10 millimeter
750 millimeter to meter
42 yard to inch
10 meter to foot样例2：
4 3
1 fortnight = 14 day
1 microcentury = 0.036525 day
1 microcentury = 1000 nanocentury
1 week = 7 day
22.2 fortnight to nanocentury
2.5 nanocentury to week
3.14 day to fortnight样例3：
10 2
1 micrometer = 1000 nanometer
1 millimeter = 1000 micrometer
1 meter = 1000 millimeter
1 kilometer = 1000 meter
1 megameter = 1000 kilometer
1 lightsecond = 299.792458 meter
1 lightminute = 60 lightsecond
1 lighthour = 60 lightminute
1 lightday = 24 lighthour
1 lightyear = 365.25 lightday
42 nanometer to lightyear
42 lightyear to nanometer

【输出样例】

样例1：
0.75
1512
impossible样例2：
8509240.2464065708427
1.3044642857142857142e-05
0.22428571428571428572样例3：
4.439403502903384947e-18
3.9735067984839359997e+20

---

题解

   把本题直接建模为图上路径问题。把单位unit看成点，把换算值value看成边，那么所有的单位换算关系式就转换成了图，图中有一些互相连通的子图。
   查询时，若两个点（两个单位）在一个连通子图上，找到路径，计算路径之积（把这条路径上的所有边的转换值累乘）就是答案；如果不在一个连通子图上，输出“impossible”。
   本题只需找到一条路径即可，并不一定需要找最短路径。用什么路径算法？如果是在普通图上找路径，应该用Dijkstra这样的算法。如果用DFS，可能需要搜天量的路径，导致超时。
   本题的连通子图是什么形状？题目限制“每个单位最多只能以一种方式转换为其他任何单位”，也就是说两个点之间只有一条路径，这意味着这个连通子图是一棵树。在一棵树上，两点间的路径只有1条，用DFS编码最简单，一次路径计算的复杂度是O(n)的。
   建图时，一个换算关系式是一条有向边，但是可以反向转换，例如“1 fortnight = 14 day”反过来是“1 day = 1/14 fortnight”。这样一条有向边实际上是双向边，或者看成无向边。
【重点】 DFS路径 。

C++代码

   代码要点是：（1）用最常用的邻接表存图；（2）用map把单位转为唯一的数字；（3）用dfs搜索一条路径，并计算路径之积。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
map<string, int>id;             //用map把单位转为唯一的数字
int cnt = 0;
int get_id(string s){           //查询单位对应的数字if(id.count(s)) return id[s];return id[s] = ++cnt;
}
vector<pair<int,ld>> G[110];           //用邻接表存图
ld dfs(int s, int fa, int t, ld ans){  //搜起点s到终点t的路径。fa是s的上一个点if(s == t)return ans;              //到达终点for(auto now : G[s]){int v = now.first;ld w = now.second;if(v == fa) continue;          //不回头ld now_ans = dfs(v, s, t, ans * w);if(now_ans > 0) return now_ans;  //返回答案}return -1;                         //没搜到路径
}
int main(){int n, q;   cin >> n >> q;while(n--){ld va, vb;string sa, sb, _;                       // _ 是 ‘=’cin >> va >> sa >> _ >> vb >> sb;G[get_id(sa)].push_back(make_pair(get_id(sb), vb));        //双向边G[get_id(sb)].push_back(make_pair(get_id(sa), 1.0 / vb));}while(q--){ld va;string sa, sb, _;cin >> va >> sa >> _ >> sb;auto ans = dfs(get_id(sa), -1, get_id(sb), va);if(ans > 0) printf("%.10Lf\n", ans);   //注意long double的输出格式else        printf("impossible\n");}return 0;
}

Java代码

import java.util.*;
public class Main {static Map<String, Integer> id = new HashMap<>();static int cnt = 0;static List<Pair<Integer, Double>>[] G = new ArrayList[110];    static int get_id(String s) {if (id.containsKey(s)) return id.get(s);cnt++;id.put(s, cnt);return cnt;}     static double dfs(int s, int fa, int t, double ans) {if (s == t) return ans;for (Pair<Integer, Double> now : G[s]) {int v = now.first;double w = now.second;if (v == fa) continue;double now_ans = dfs(v, s, t, ans * w);if (now_ans > 0) return now_ans;}return -1;}     public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), q = sc.nextInt();for (int i = 1; i <= Math.min(n+n, 101); i++) G[i] = new ArrayList<>();while (n-- > 0) {double va, vb;String sa, sb, e;va = sc.nextDouble();sa = sc.next();e = sc.next();vb = sc.nextDouble();sb = sc.next();G[get_id(sa)].add(new Pair<>(get_id(sb), vb));G[get_id(sb)].add(new Pair<>(get_id(sa), 1 / vb));}while (q-- > 0) {double va;String sa, sb, e;va = sc.nextDouble();sa = sc.next();e = sc.next();sb = sc.next();double ans = dfs(get_id(sa), -1, get_id(sb), va);if (ans > 0) System.out.printf("%.10f\n", ans);else System.out.println("impossible");}}
} 
class Pair<A, B> {A first;B second;     Pair(A first, B second) {this.first = first;this.second = second;}
}

Python代码

import sys
sys.setrecursionlimit(1000000)
id = {}  #用字典把单位转为唯一的数字
cnt = 0
G = [[] for _ in range(200)]  # 邻接表存图
def get_id(s):global cntif s in id:  return id[s]cnt += 1id[s] = cntreturn cnt
def dfs(s, fa, t, ans):if s == t:   return ansfor v, w in G[s]:if v == fa:   continuenow_ans = dfs(v, s, t, ans * w)if now_ans > 0:  return now_ansreturn -1
n, q = map(int, input().split())
for i in range(n):va, sa, _, vb, sb = input().split()va, vb = float(va), float(vb)u, v = get_id(sa), get_id(sb)G[u].append((v, vb))G[v].append((u, 1.0 / vb))
for i in range(q):va, sa, _, sb = input().split()va = float(va)u, v = get_id(sa), get_id(sb)ans = dfs(u, -1, v, va)if ans > 0:  print(ans)  else:        print("impossible")