题目链接
https://www.patest.cn/contests/gplt/L3-015
思路 用一个 数组标记 胜负 每次输入一行字符串 然后遍历 如果 碰到 W 那么 vis[i][j] = 1; 如果 碰到 L 那么 vis[j][i] = 1;
然后 食物链 中 所有队伍都有 而且要保持 字典序 最小 那么毫无疑问 第一个 必然是 1 所以 就从 dfs(int cur, int step) cur 表示 搜到第几支队伍 step 表示搜到第几步了
然后 如果剩下未标记的队伍 都没有 战胜 队伍1 的 那么就要剪去了 因为 再往下搜 也是 不能构成食物链的
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 5; const int MOD = 1e9 + 7; string s[25]; int vis[20][20]; map <int, int> m; vector <int> v; int ans, n; void dfs(int cur, int step) { if (ans == 1) return; if (step == n && ans == -1) { if (vis[cur][0]) ans = 1; return; } else { bool cut = false; for (int i = 0; i < n; i++) { if (m[i] == 0 && vis[i][0]) cut = true; } if (cut == false) return; for (int i = 0; i < n && ans == -1; i++) { if (m[i] == 0 && vis[cur][i]) { v.push_back(i); m[i] = 1; dfs(i, step + 1); if (ans == -1) { m[i] = 0; v.pop_back(); } else return; } } } } int main() { memset(vis, 0, sizeof(vis)); scanf("%d", &n); for (int i = 0; i < n; i++) { cin >> s[i]; for (int j = 0; j < n; j++) if (s[i][j] == 'W') vis[i][j] = 1; else if (s[i][j] == 'L') vis[j][i] = 1; } int flag = 1; for (int i = 1; i < n; i++) { if (vis[i][0]) { flag = 0; break; } } if (flag) printf("No Solution\n"); else { ans = -1; v.clear(); m.clear(); v.push_back(0); m[0] = 1; dfs(0, 1); if (ans == -1) printf("No Solution\n"); else { vector <int>::iterator it; for (it = v.begin(); it != v.end(); it++) { if (it != v.begin()) printf(" "); cout << (*it) + 1; } cout << endl; } } }转载于:https://www.cnblogs.com/Dup4/p/9433229.html
相关资源：JAVA上百实例源码以及开源项目