题解 P2951 【[USACO09OPEN]捉迷藏Hide and Seek】

实际上这题不需要这么麻烦： 对整个图进行广度优先遍历得出深度，其中深度最大的点就是最远的，然后我们找出有几个这样的点即可 贴代码： ------------ ```cpp #define maxn 20000+50 #include<cstdio> #include<algorithm> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> using namespace std; int n,m; queue<int> q; //队列 vector<int> g[maxn]; //懒人vector存图 int step[maxn],vis[maxn]; //深度和标记 int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;++i) { int u,v; scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } memset(step,-1,sizeof(step)); memset(vis,0,sizeof(vis)); step[1]=0; q.push(1); vis[1]=1; //源点入队 while (!q.empty()) { int u=q.front(); // printf("%d\n",u); q.pop(); for (int i=0;i<g[u].size();++i) { int v=g[u][i]; if (!vis[v]) { step[v]=step[u]+1; q.push(v); vis[v]=1; } } } /* for (int i=1;i<=n;++i) printf("%d ",step[i]); puts("");*/ int ans=0,ansp,ansnum=0; for (int i=1;i<=n;++i) if (ans<step[i]) { ans=step[i]; ansp=i; } for (int i=1;i<=n;++i) if (ans==step[i]) ansnum++; printf("%d %d %d\n",ansp,ans,ansnum); return 0; } ```