团体天梯 L3-015 球队“食物链” （30 分） https://blog.csdn.net/qq_40946921/article/details/87939254?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.channel_param&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.channel_param
#include<iostream> #include<vector> using namespace std; int graph[20][20], visited[20]; int n,T0; //T0为首支队伍 vector<int> result; bool cut() { //剪枝：当剩余队伍中不存在战胜第一支队伍，那么这条线就没必要继续深入 for (int i = 0; i < n; i++) if (!visited[i] && graph[i][T0]) return 1; return 0; } void search(int i,int k) { for (int j = 0; cut()&&j < n; j++) { if (!visited[j]&&graph[i][j]) { visited[j] = 1; result.push_back(j); if (k == n-2&&graph[j][T0]) { //最后一支队伍可以战胜首队 for (int i = 0; i < result.size(); i++) cout << (i ? " " : "") << result[i]+1; exit(0); //找到的第一个就是字典序最小的，直接结束程序 } else search(j, k + 1); result.pop_back(); //回溯 visited[j] = 0; } } } int main() { cin >> n; char ch; for(int i=0;i<n;i++) for (int j = 0; j < n; j++) { cin >> ch; if (ch == 'W') graph[i][j] = 1; //W为i战胜j else if (ch == 'L') graph[j][i] = 1; //L为i败于j，即j战胜i } for (int i = 0; i < n; i++) { T0 = i; result.push_back(T0); visited[T0] = 1; search(T0, 0); //以不同队伍为首队进行搜索 visited[T0] = 0; result.pop_back(); } cout << "No Solution"; return 0; }