dfs遍历，回溯剪枝取最佳解
#include<iostream>#include<vector>#include<string>#define INF 0x3f3f3fusing namespace std;struct VNode { string name; int grade; VNode() { grade = 0; }};vector<vector<int>> arc = {};//邻接矩阵vector<VNode> vex;//顶点int N, K,M;int Find_V(string str)//寻找str的位置{ for (int t = 0;t < N;t++) if (str == vex[t].name)return t;}struct resault {//存储结果的结构 int sumgrade; int num; int length; vector<int> Path; resault() { sumgrade = num = length = 0; } bool Operator<(const resault b)const { return length<b.length || (length == b.length && sumgrade>b.sumgrade) || (length == b.length && sumgrade == b.sumgrade && num < b.num); }};resault re, te;//结果、中间与结果比较的节点vector<int> visited;//dfs中保存是否访问过int cnt=1;void dfs(int index){ if (re.length < te.length) return;//剪枝 if (index == M)//结果比较 { if (te.length < re.length) { cnt = 1; re = te; } else { cnt++; if (te < re) re = te; } return; } for (int t = 0;t < N;t++) if (visited[t] == 0 && arc[index][t] != 0) { visited[t] = 1; te.length += arc[index][t]; te.num++; te.sumgrade += vex[t].grade; te.Path.push_back(t); dfs(t); visited[t] = 0;//回溯 te.length -= arc[index][t]; te.num--; te.sumgrade -= vex[t].grade; te.Path.pop_back(); }}int main(){ cin >> N >> K; arc.resize(N); vex.resize(N); cin >> vex[0].name; arc[0].resize(N); visited.resize(N); for (int t = 1;t < N;t++) { arc[t].resize(N); cin >> vex[t].name >> vex[t].grade; if (vex[t].name == "ROM") M = t; } for (int t = 0;t < K;t++) { string str1, str2; int a,b,c; cin >> str1 >> str2 >> c; a = Find_V(str1);b = Find_V(str2); arc[a][b] = arc[b][a] = c; } visited[0] = 1; re.length = INF; dfs(0); cout << cnt << " " << re.length << " " << re.sumgrade << " " << re.sumgrade / re.num << endl<<vex[0].name; for (auto x:re.Path) { cout << "->" << vex[x].name; } cout << endl;}新闻热点
疑难解答
