本文共 2202 字，大约阅读时间需要 7 分钟。
题意:任意一个点都至少有一个点与其相连接,所有的点可以进行任意排列,总排列数为n!.
一个点带宽定义与它相连的点的最远距离,一个排列的带宽定义为,点中最大的带宽,找出带宽最小的那个排列,有多组,输出字典序最小
#include #include #include #include #include #include #include #include #include using namespace std;char v[8];char edge[100][100];int tv = 0;char res[8];int maxl = 0x7fffffff;int com(char r[]){ int max = -1; for(int i = 0; i < tv; i++) { char c = r[i]; for(int j = 0; j < 100; j++) { if(edge[c][j] == '\0') break; char cc = edge[c][j]; int k = 0; for(k = 0; k < tv; k++) { if(r[k] == cc) break; } int l = k - i; l = l < 0 ? l * -1 : l; max = max < l ? l : max; } } if(max < maxl) { maxl = max; memcpy(res, r, sizeof(char) * tv); } return 0;}void dfs(int cur, int vis[], char r[]){ if(cur == tv) { com(r); return; } for(int i = 0; i < tv; i++) { if(vis[i] == 1) continue; vis[i] = 1; r[cur] = v[i]; cur++; dfs(cur, vis, r); cur--; vis[i] = 0; }}void sort(){ for(int i = 0; i < tv; i++) { for(int j = 1; j < tv - i; j++) { if(v[j - 1] > v[j]) { char t = v[j - 1]; v[j - 1] = v[j]; v[j] = t; } } }}int main(){ //freopen("d:\\1.txt", "r", stdin); while (cin) { string str; cin >> str; if(str == "#") break; istringstream is(str); memset(edge, '\0', sizeof(edge)); memset(v, '\0', sizeof(v)); tv = 0; maxl = 0x7fffffff; int index[100]; int mark[100][100]; int mark2[100]; memset(index, 0, sizeof(index)); memset(mark, 0, sizeof(mark)); memset(mark2, 0, sizeof(mark2)); char c; char cc; while (is >> c) { if(c == ':') { continue; } if(c == ';') { is >> cc; if(mark2[cc] == 0) { v[tv++] = cc; mark2[cc] = 1; } continue; } if(tv == 0) { cc = c; mark2[cc] = 1; v[tv++] = cc; continue; } if(mark[cc][c] != 1) { edge[cc][index[cc]++] = c; mark[cc][c] = 1; } if(mark[c][cc] != 1) { edge[c][index[c]++] = cc; mark[c][cc] = 1; } if(mark2[c] == 0) { mark2[c] = 1; v[tv++] = c; } } //枚举 int vis[10]; memset(vis, 0, sizeof(vis)); char r[8]; sort(); dfs(0, vis, r); for(int i = 0; i < tv; i++) cout << res[i] << " "; cout << "-> " << maxl << endl; } return 0;}
转载于:https://www.cnblogs.com/shuiyonglewodezzzzz/p/7623786.html