【PAT甲级】1179 Chemical Equation（30分）[dfs，搜索与回溯，排序]

问题思考：

• 题目问每种 product 的生成化学方程式，要求使用过的 reactant 不重复。而且题目给定了一些方程式，那么解空间就限定在这些方程式外加 “自反应恒等式” 了。
• 解空间有限，自然想到可以用搜索与回溯的路子。即一旦在搜索过程中出现了重复使用某一 reactant 就可以回溯并调转搜索方向。
• 搜索前对反应式进行 “从小到大” 的排序，确保搜索过程有序稳步进行。自定义的排序需要借助结构体实现起来方便一些。
• 测试点2是关于反应物是否存在的，如果没判断反应物是否存在则测试点2错误。

代码实现：

#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;
}