題目鏈接：https://www.lydsy.com/JudgeOnline/problem.php?id=4956
?
暫時結束DP的學習，開始圖論的復習了，哦，復習，呵呵呵。。。
這是比較水的一道題，我們只關注從一個點是否有路徑可以到達另一個點，而且數據范圍又不大，顯然是Floyd算法的應用，求傳遞閉包。
但是，好好讀題，把題目的要求在代碼當中體現得淋漓盡致，別問我為什么要說這個。。。
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxa = 30, maxn = 55; 5 6 int f[maxa][maxa]; 7 char w1[maxn], w2[maxn]; 8 9 int main() { 10 int m, n; 11 char a, b; 12 scanf("%d%d", &m, &n); 13 for (int i = 1; i <= m; ++i) { 14 a = getchar(); 15 while (a < 'a' || a > 'z') a = getchar(); 16 b = getchar(); 17 while (b < 'a' || b > 'z') b = getchar(); 18 a = a - 'a' + 1, b = b - 'a' + 1; 19 f[(int)a][(int)b] = 1; 20 } 21 for (int i = 1; i <= 26; ++i) f[i][i] = 1; 22 for (int k = 1; k <= 26; ++k) 23 for (int i = 1; i <= 26; ++i) 24 for (int j = 1; j <= 26; ++j) 25 f[i][j] = f[i][j] || (f[i][k] && f[k][j]); 26 for (int i = 1; i <= n; ++i) { 27 scanf("%s%s", w1, w2); 28 int w1l = strlen(w1), w2l = strlen(w2), flag = 1; 29 if (w1l != w2l) { 30 printf("no\n"); 31 continue; 32 } 33 for (int j = 0; j < w1l; ++j) 34 if (!f[(int)w1[j] - 'a' + 1][(int)w2[j] - 'a' + 1]) { 35 printf("no\n"); 36 flag = 0; 37 break; 38 } 39 if (flag) printf("yes\n"); 40 } 41 return 0; 42 }
?
