赞
踩
问题思考:
代码实现:
- #include<iostream>
- #include<cstring>
- #include<vector>
- #include<unordered_map>
- #include<algorithm>
- using namespace std;
-
- struct Equation {
- vector<int> e;
- bool operator < (const Equation &x) {
- int n = e.size(), m = x.e.size();
- for (int i = 0; i < n && i < m; i++) {
- if (e[i] != x.e[i]) return e[i] < x.e[i];
- }
- }
- };
-
- int n, m, k, flag, f[100], r[100], isExit[100]; // flag标记是否找到solution;f数组标记当前prod用到哪一个equation了;r数组标记当前reactant使用的次数;isExit数组用来判断equation中的reactant是否存在
- vector<int> reac, prod;
- unordered_map<int, vector<Equation>> equa;
-
- // 初始化
- void init() {
- // cin
- scanf("%d", &n);
- for (int i = 0, r; i < n; i++) {
- scanf("%d", &r);
- reac.push_back(r);
- isExit[r] = 1;
- }
-
- scanf("%d", &m);
- for (int i = 0, p; i < m; i++) {
- scanf("%d", &p);
- prod.push_back(p);
- }
-
- scanf("%d", &k);
- getchar();
- for (int i = 0; i < k; i++) {
- // get a line
- string equation;
- getline(cin, equation);
-
- // Parse equation
- int arrowPos = equation.find("->");
- string productPart = equation.substr(arrowPos + 3);
- string reactantPart = equation.substr(0, arrowPos);
-
- // classify equations into different product
- int product = stoi(productPart);
- Equation tmp;
- for (int j = 0; j < reactantPart.size(); j += 5) {
- tmp.e.push_back(stoi(reactantPart.substr(j, 2)));
- }
- equa[product].push_back(tmp);
- }
-
- // sort
- for (auto x : prod) {
- // don't forget to add the "self reaction"
- if (find(reac.begin(), reac.end(), x) != reac.end()) {
- equa[x].push_back(Equation{vector<int>({x})});
- }
- sort(equa[x].begin(), equa[x].end());
- }
- return ;
- }
-
- // 搜索解空间
- void dfs(int cnt) {
- if (cnt == m) {
- for (auto it : reac) {
- if (r[it] > 1) return ;
- }
- flag = 1;
- return ;
- }
- for (int i = 0; i < equa[prod[cnt]].size(); i++) {
- if (flag == 1) return ;
- f[prod[cnt]] = i;
- // 剪枝优化
- int flag1 = 0;
- for (auto it : equa[prod[cnt]][i].e) {
- if (r[it] > 1) return;
- if (!isExit[it]) flag1 = 1;
- }
- if (flag1) continue;
- // 搜索与回溯
- for (auto it : equa[prod[cnt]][i].e) r[it] += 1;
- dfs(cnt + 1);
- for (auto it : equa[prod[cnt]][i].e) r[it] -= 1;
- }
- return ;
- }
-
- // 输出结果
- void output() {
- for (int i = 0; i < m; i++) {
- int p = prod[i];
- vector<int> e = equa[p][f[p]].e;
- if (e.size() == 1 && e[0] == p) {
- printf("%02d -> %02d\n", p, p);
- } else {
- for (int j = 0; j < e.size(); j++) {
- j && printf(" + ");
- printf("%02d", e[j]);
- }
- printf(" -> %02d\n", p);
- }
- }
- return ;
- }
-
- int main() {
- init();
- dfs(0);
- output();
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。