. . 题意：给出n个字符串，字符串可以进行3种操作变换：1、换其中一个字母 2、从中增加一个字母 3、从中去掉一个字母。问从n个字符串进行变换，求最长的变换序列 . . 解法：可以变换的连一条边，然后每个点暴力bfs就好了 . .
#include <iostream> #include <string> #include <string.h> using namespace std; const int maxn = 5100; string a[maxn]; int dist[maxn], n, d[maxn]; int tar[maxn], nextt[maxn], last[maxn], tot, ans; bool check(int x, int y) { if (a[x].size() == a[y].size()) { int sum = 0; for (int i = 0; i < a[x].size(); i++) if (a[x][i] != a[y][i]) sum++; if (sum <= 1) return true; else return false; } if (a[x].size() == a[y].size()+1) { int sum = 0; int s = 0, t = 0; while (1) { if (a[x][s] != a[y][t]) { s++; sum++; } if (a[x][s] != a[y][t]) { s++; sum++; } if (sum > 1) return false; s++; t++; if (s == a[x].size()) break; if (t == a[y].size()) break; } return true; } if (a[x].size()+1 == a[y].size()) { int sum = 0; int s = 0, t = 0; while (1) { if (a[x][s] != a[y][t]) { t++; sum++; } if (a[x][s] != a[y][t]) { t++; sum++; } if (sum > 1) return false; s++; t++; if (s == a[x].size()) break; if (t == a[y].size()) break; } return true; } return false; } void insert(int x, int y) { tot++; tar[tot] = y; nextt[tot] = last[x]; last[x] = tot; } int main() { while (scanf("%d", &n) != EOF) { tot = 0; memset(last, 0, sizeof(last)); if (n == 0) break; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++) if (check(i, j)) { insert(i, j); insert(j, i); } ans = 1; for (int i = 1; i <= n; i++) { memset(dist, 255, sizeof(dist)); dist[i] = 1; d[1] = i; int s = 0, t = 1; while (s != t) { s++; if (dist[d[s]] > ans) ans = dist[d[s]]; int k = last[d[s]]; while (k != 0) { if (dist[tar[k]] != -1) { k = nextt[k]; continue; } dist[tar[k]] = dist[d[s]]+1; t++; d[t] = tar[k]; k = nextt[k]; } } } printf("%d\n", ans); } }