Solution
因为 \(k\) 的值较小，所以这题可以直接暴力枚举。
如果 \(k = 2\)，直接输出 \(g\) 数组就可以了。
void solve2() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(g[i][j] ? 'Y' : 'N');putchar('\n');}
}
如果 \(k = 3\)，枚举中间点 \(p\)，然后找到和 \(p\) 相连的两点 \(i\) 和 \(j\)，只要 \(i \ne j\)，\(\left(i, j\right)\) 就是合法的。
void solve3() {memset(f, false, sizeof(f));for (int k = 1; k <= n; k++) // 枚举中间点for (auto i : e[k])for (auto j : e[k])if (i != j) f[i][j] = true;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(f[i][j] ? 'Y' : 'N');putchar('\n');}
}
如果 \(k = 4\)，枚举起点 \(i\) 和终点 \(j\)，然后分别枚举和 \(i\) 相连的 \(p\) 以及和 \(j\) 相连的 \(q\)，只要 \(i\)，\(j\)，\(p\)，\(q\) 四个数不相等，并且 \(p\) 和 \(q\) 相连，\(\left(i, j\right)\) 就是合法的。
void solve4() {memset(f, false, sizeof(f));for (int i = 1; i <= n; i++) // 枚举起点for (int j = 1; j < i; j++) { // 枚举终点bool flag = 0;// 枚举中间点for (auto p : e[i]) { if (p != j) {for (auto q : e[j])if (q != i && q != p && g[p][q]) { // (i,j)合法flag = 1;break;}if (flag) break;}if (flag) break;}f[i][j] = f[j][i] = flag;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(f[i][j] ? 'Y' : 'N');putchar('\n');}
}
当 \(5 \le k \le 7\)，作法和 \(k = 4\) 时差不多，枚举起点和终点，然后依次枚举相连的中间点，只要这些数不同，这对起点和终点就是合法的。
例如，当 \(k = 5\) 时，代码如下：
void solve5() {memset(f, false, sizeof(f));for (int i = 1; i <= n; i++) // 枚举起点for (int j = 1; j < i; j++) { // 枚举终点bool flag = 0;// 枚举中间点for (auto p : e[i]) {if (p != j) {for (auto q : e[j])if (q != i && q != p) {for (auto s : e[p])if (s != i && s != j && s != q && g[s][q]) { // (i,j)合法flag = 1;break;}if (flag) break;}if (flag) break;}if (flag) break;}f[i][j] = f[j][i] = flag;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(f[i][j] ? 'Y' : 'N');putchar('\n');}
}
多测要初始化。
Code
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, k;
bool g[N][N], f[N][N];
vector<int> e[N];
void add(int u, int v) {e[u].push_back(v);
}
void solve2() {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(g[i][j] ? 'Y' : 'N');putchar('\n');}
}
void solve3() {memset(f, false, sizeof(f));for (int k = 1; k <= n; k++) // 枚举中间点for (auto i : e[k])for (auto j : e[k])if (i != j) f[i][j] = true; // (i,j)合法for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(f[i][j] ? 'Y' : 'N');putchar('\n');}
}
void solve4() {memset(f, false, sizeof(f));for (int i = 1; i <= n; i++) // 枚举起点for (int j = 1; j < i; j++) { // 枚举终点bool flag = 0;// 枚举中间点for (auto p : e[i]) { if (p != j) {for (auto q : e[j])if (q != i && q != p && g[p][q]) { // (i,j)合法flag = 1;break;}if (flag) break;}if (flag) break;}f[i][j] = f[j][i] = flag;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(f[i][j] ? 'Y' : 'N');putchar('\n');}
}
void solve5() {memset(f, false, sizeof(f));for (int i = 1; i <= n; i++) // 枚举起点for (int j = 1; j < i; j++) { // 枚举终点bool flag = 0;// 枚举中间点for (auto p : e[i]) {if (p != j) {for (auto q : e[j])if (q != i && q != p) {for (auto s : e[p])if (s != i && s != j && s != q && g[s][q]) { // (i,j)合法flag = 1;break;}if (flag) break;}if (flag) break;}if (flag) break;}f[i][j] = f[j][i] = flag;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(f[i][j] ? 'Y' : 'N');putchar('\n');}
}
void solve6() {memset(f, false, sizeof(f));for (int i = 1; i <= n; i++) // 枚举起点for (int j = 1; j < i; j++) { // 枚举终点bool flag = 0;// 枚举中间点for (auto p : e[i]) {if (p != j) {for (auto q : e[j])if (q != i && q != p) {for (auto s : e[p])if (s != i && s != j && s != q) {for (auto t : e[q])if (t != s && t != p && t != i && t != j && g[s][t]) { // (i,j)合法flag = 1;break;}if (flag) break;}if (flag) break;}if (flag) break;}if (flag) break;}f[i][j] = f[j][i] = flag;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(f[i][j] ? 'Y' : 'N');putchar('\n');}
}
void solve7() {memset(f, false, sizeof(f));for (int i = 1; i <= n; i++) // 枚举起点for (int j = 1; j < i; j++) { // 枚举终点bool flag = 0;// 枚举中间点for (auto p : e[i]) {if (p != j) {for (auto q : e[j])if (q != i && q != p) {for (auto s : e[p])if (s != i && s != j && s != q) {for (auto t : e[q])if (t != s && t != p && t != i && t != j) {for (auto x : e[s])if (x != t && x != p && x != q && x != i && x != j && g[x][t]) { // (i,j)合法flag = 1;break;}if (flag) break;}if (flag) break;}if (flag) break;}if (flag) break;}if (flag) break;}f[i][j] = f[j][i] = flag;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) putchar(f[i][j] ? 'Y' : 'N');putchar('\n');}
}
int main() {int T;scanf("%d", &T);while (T--) {memset(g, false, sizeof(g));scanf("%d%d%d", &n, &m, &k);for (int i = 1; i <= n; i++) e[i].clear();for (int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);if (u == v) continue;add(u, v), add(v, u), g[u][v] = g[v][u] = true;}if (k == 2) solve2();if (k == 3) solve3();if (k == 4) solve4();if (k == 5) solve5();if (k == 6) solve6();if (k == 7) solve7();}return 0;
}