题目链接:点击打开链接
题目大意:略。
解题思路:略。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; const int maxn=10005; int vis[maxn], mp[maxn][maxn]; int n,m; int bfs(int len) { // 最后一个结点,尾巴,每个点的最终结果,6层范围内的数,临时节点 int last=len,tail=0,cnt=1,lvl=0,tmp; vis[len]=1; queue<int> que; que.push(len); while(!que.empty()) { tmp=que.front(); que.pop(); for(int i=1;i<=n;i++) { if(mp[tmp][i] && !vis[i]) // 有边且未被访问过 { cnt++; vis[i]=1; tail=i; // 为了每一层最后一个的节点标记 que.push(i); } } if(tmp==last) { last=tail; lvl++; } if(lvl==6) break; } return cnt; } int main() { scanf("%d%d",&n,&m); // mem(mp,0); // 内存超限 int u,v; for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); mp[u][v]=mp[v][u]=1; } for(int i=1;i<=n;i++) { mem(vis,0); printf("%d: %.2f%%\n",i,bfs(i)*100.0/n); } return 0; }