题目链接。
分析:
只要将互相认识的人之间的权值赋值为1,并用Floyd算法
然后检查任意两人间的最短路是否大于7即可
#include <stdio.h> #include <string.h> #define MAXN 110 const int INF = (1<<28); int w[MAXN][MAXN], d[MAXN][MAXN]; void Floyd(int n){ int i, j, k; for(i=0; i<n; i++){ for(j=0; j<n; j++){ if(w[i][j] != INF) d[i][j] = w[i][j]; else if(i == j) d[i][j] = 0; else d[i][j] = INF; } } for(k=0; k<n; k++){ for(i=0; i<n; i++){ if(d[i][k] < INF) for(j=0; j<n; j++){ if(d[k][j] < INF && d[i][k]+d[k][j] < d[i][j]) d[i][j] = d[i][k]+d[k][j]; } } } } int main(){ int n, m, i, j, a, b, flag; while(scanf("%d %d", &n, &m) == 2){ flag = 1; for(i=0; i<n; i++) for(j=0; j<n; j++) w[i][j] = INF; for(i=0; i<m; i++){ scanf("%d %d", &a, &b); w[a][b] = w[b][a] = 1; } Floyd(n); for(i=0; i<n && flag; i++){ for(j=0; j<n && flag; j++){ if(d[i][j]-1 > 6){printf("No\n"); flag =0;} } } if(flag) printf("Yes\n"); } return 0; }