7-4 Chemical Equation (30 分)
A chemical equation is the symbolic representation of a chemical reaction in the form of symbols and formulae, wherein the reactant entities are given on the left-hand side and the product entities on the right-hand side. For example, $$CH_4+2O_2=CO_2+2H_2O$$
means that the reactants in this chemical reaction are methane and oxygen: CH4 and O2, and the products of this reaction are carbon dioxide and water: CO2 and H2O.
Given a set of reactants and products, you are supposed to tell that in which way we can obtain these products, provided that each reactant can be used only once. For the sake of simplicity, we will consider all the entities on the right-hand side of the equation as one single product.
Input Specification:
Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤20), followed by N distinct indices of reactants. The second line gives an integer M (1≤M≤10), followed by M distinct indices of products. The index of an entity is a 2-digit number.
Then a positive integer K (≤50) is given, followed by K lines of equations, in the format:
$$
reactant_1 + reactant_2 + … + reactant_n -> product
$$
where all the reactants are distinct and are in increasing order of their indices.
Note: It is guaranteed that
- one set of reactants will not produce two or more different products, i.e. situation like 01 + 02 -> 03 and 01 + 02 -> 04 is impossible;
- a reactant cannot be its product unless it is the only one on the left-hand side, i.e. 01 -> 01 is always true (no matter the equation is given or not), but 01 + 02 -> 01 is impossible; and
- there are never more than 5 different ways of obtaining a product given in the equations list.
Output Specification:
For each case, print the equations that use the given reactants to obtain all the given products. Note that each reactant can be used only once.
Each equation occupies a line, in the same format as we see in the inputs. The equations must be print in the same order as the products given in the input. For each product in order, if the solution is not unique, always print the one with the smallest sequence of reactants — A sequence $${ a_1,⋯,a_m }$$ is said to be smaller than another sequence $${ b_1 ,⋯,b_n } $$if there exists $$1≤i≤min(m,n)$$ so that $$a_j =b_j \;\; for \;\;all\;\; j<i, and\;\; ai <bi.$$
It is guaranteed that at least one solution exists.
Sample Input:
8 09 05 03 04 02 01 16 10
3 08 03 04
6
03 + 09 -> 08
02 + 08 -> 04
02 + 04 -> 03
01 + 05 -> 03
01 + 09 + 16 -> 03
02 + 03 + 05 -> 08Sample Output:
02 + 03 + 05 -> 08
01 + 09 + 16 -> 03
04 -> 04题目要求
题目粗心
给定n个反应物，m个生成物和k个化学反应方程式。要求依据反应物和化学方程式输入能够取得生成物的化学方程式，生成规定如下：
- 1、一组反应物只会生成一种product
- 2、除了 pro->pro 的状况，一个化学方程式是不可能呈现反应物中存在生成物的状况
- 3、对于有多个生成的化学式输入字典序最小的那个。
- 4、每一种反应物只能应用一次
算法思路
此题如同只能应用深度优先遍从来解决，起因在于须要将所有的生成物进行生成，并且题目保障肯定存在一个解。那么应用贪婪算法取每一次取得以后生成物字典序最小的有可能会导致前面的生成物无奈生成的状况。为了不便进行搜寻咱们应用构造体Equation来封装咱们须要的数据，这里将算法的过程分为预处理和DFS。
- 数据结构：
struct Equation {
string equation;
vector<int> reacts;
int prod{};
friend bool operator<(const Equation &a, const Equation &b) {
return a.equation < b.equation;
}
};
unordered_map<int, bool> reactants;// 标记以后反应物是否能够应用
unordered_map<int, set<Equation>> products;// 依据product建设到所有生成该生成物的Equation汇合
vector<int> pro;// 所有须要生成的生成物编号
vector<string> ans;// 所有的后果汇合数据的预处理
首先在输出所有反应物的时候标记reactants[index] = true，在输出生成物的时候须要建设product->product这样的方程式增加到products汇合中，并同时标记以后成物为反应物。最初在输出每一行的化学方程式的时候应用process函数进行解决，将其封装为一个Equation，并增加到products汇合中。
DFS
咱们应用输出的生成物数组pro的下标来代表以后搜寻的地位，起始为0，终止地位为m-1，DFS(proCur,proEnd)的含意为数组[proCur,proEnd-1]的生成物是否能够被生成，如果能够返回true,否则返回false。那么原问题的解就是DFS(0,m)。那么递归边界和递归体别离为：
- 递归边界：当咱们以后遍历的下标为m的时候阐明遍历结束，取得了一组解，间接返回true。
- 递归体：首先遍历以后生成物pro[proCur]的所有化学方程式，判断以后的方程是是否能够应用，如果能够，先标记以后化学方程式的生成物全副曾经应用，并将方程式增加到ans数组中，而后进行下一层递归，判断proCur + 1以及后续的生成物是否能够被生成，如果为true，阐明从proCur地位到数组开端的所有生成物都能够被生成，返回true。否则阐明后续生成物生成失败，须要回溯，先将所有的反应物标记为未应用，而后ans弹出之前增加的方程式。
留神点
- 1、这里应用DFS次要是因为须要生成所有的生成物，一个都不能落下，所以贪婪算法不可用，测试点1和5考查该点。
- 2、每一个查问的生成物都能够生成 product->product的化学方程式，须要人为增加该式子到汇合中。
提交后果
AC代码
#include<cstdio>
#include<vector>
#include<iostream>
#include<unordered_map>
#include <set>
#include <string>
using namespace std;
struct Equation {
string equation;
vector<int> reacts;
int prod{};
friend bool operator<(const Equation &a, const Equation &b) {
return a.equation < b.equation;
}
};
unordered_map<int, bool> reactants;// 标记以后反应物是否能够应用
unordered_map<int, set<Equation>> products;// 依据product建设到所有生成该生成物的Equation汇合
vector<int> pro;// 所有须要生成的生成物编号
vector<string> ans;// 所有的后果汇合
// 将s封装为一个Equation
void process(const string &s) {
int n = s.size();
if (n == 0) {
return;
}
Equation e;
// 最初两位为生成物编号
e.prod = stoi(s.substr(n - 2));
// 合成字符串获取反应物
string temp;
for (int i = 0; i < n; ++i) {
if (s[i] >= '0' && s[i] <= '9') {
temp.push_back(s[i]);
} else if (s[i] == ' ' && !temp.empty()) {
int v = stoi(temp);
e.reacts.push_back(v);
temp.clear();
} else if (s[i] == '-') {
break;
}
}
e.equation = s;
products[e.prod].insert(e);
}
// 判断以后的生成物pro[proCur]是否能够被生成，如果不能够就得回溯
bool DFS(int proCur, int proEnd) {
if (proCur == proEnd) {
// 此时曾经将所有的生成物生成结束
return true;
}
// 生成物编号
int proNo = pro[proCur];
// 遍历以后生成物proNo的所有化学方程式
for (const auto &allEquations:products[proNo]) {
// 判断以后的方程是是否能够应用（所有的反应物是否都没有被应用过）
bool isvalid = true;
for (int react:allEquations.reacts) {
if (!reactants[react]) {
// 以后反应物被应用过
isvalid = false;
break;
}
}
if (!isvalid) {
continue;
}
// 存在一种解
ans.push_back(allEquations.equation);
// 而后将所有的反应物都进行标记应用过
for (int react:allEquations.reacts) {
reactants[react] = false;
}
// 递归查问后续的生成物是否能够生成
if (DFS(proCur + 1, proEnd)) {
// 能够生成阐明找到了一组解，间接返回即可
return true;
}
// 以后抉择的化学方程式使得后续的生成物无奈生成，须要回溯
for (int react:allEquations.reacts) {
reactants[react] = true;
}
ans.pop_back();
}
// 遍历了所有的化学生成式都没有方法取得以后生成物
return false;
}
int main() {
// n为反应物数量，m为生成物数量
int n, m;
scanf("%d", &n);
int index;
for (int i = 0; i < n; ++i) {
scanf("%d", &index);
// 标记所有给出的反应式
reactants[index] = true;
}
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
string s;
cin >> s;
pro.push_back(stoi(s));
// 每一个反应物都存在一个 pro->pro 的化学方程式
Equation e;
e.equation.append(s);
e.equation.append(" -> ");
e.equation.append(s);
e.prod = pro[i];
e.reacts.push_back(pro[i]);
// 标记以后的生成物同时为反应物
reactants[pro[i]] = true;
// 将以后的pro->pro的化学方程式增加到products汇合中
products[pro[i]].insert(e);
}
int k;
scanf("%d", &k);
// 排汇回车
getchar();
string s;
for (int i = 0; i < k; ++i) {
getline(cin, s);
// 解决每一个化学方程式，封装为Equation
process(s);
}
// 深度搜寻，保障取得所有的生成物
DFS(0, m);
// 输入后果汇合
for (const auto &v:ans) {
cout << v << endl;
}
return 0;
}
发表回复