树的直径
No.1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include<bits/stdc++.h> const int maxn=100020; using namespace std; int dis[maxn],ans; bool vis[maxn]; vector<pair<int,int> > V[maxn]; int bfs(int x) { memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(x); vis[x]=1; int point=0; while(!Q.empty()) { int F=Q.front(); Q.pop(); if(dis[F]>ans) { ans=dis[F]; point=F; } pair<int,int>t; for(int i=0;i<V[F].size();i++) { t=V[F][i]; if(vis[t.first]==0) { vis[t.first]=1; dis[t.first]=dis[F]+t.second; Q.push(t.first); } } } return point; } int main() { int N,M,x,y,z; char dir; while(cin>>N>>M) { for(int i=0;i<M;i++) { cin>>x>>y>>z>>dir; V[x].push_back(make_pair(y,z)); V[y].push_back(make_pair(x,z)); } ans=0; int point=bfs(1); ans=0; bfs(point); cout<<ans<<endl; for(int i=0;i<=N;i++) V[i].clear(); } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #include<bits/stdc++.h> using namespace std; char MAP[1020][1020]; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int dis[1020][1020]; int N,M,fx,fy; int bfs(int x,int y) { int ans=0; memset(dis,-1,sizeof(dis)); queue<int>Q; Q.push(x); Q.push(y); dis[x][y]=0; while(!Q.empty()) { x=Q.front();Q.pop(); y=Q.front();Q.pop(); for(int i=0;i<4;i++) { int nx=dx[i]+x; int ny=dy[i]+y; if(nx>=0&&nx<M&&ny>=0&&ny<N&&MAP[nx][ny]=='.'&&dis[nx][ny]==-1) { Q.push(nx); Q.push(ny); dis[nx][ny]=dis[x][y]+1; if(ans<dis[nx][ny]) { ans=dis[nx][ny]; fx=nx; fy=ny; } } } } return ans; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&N,&M); bool flag=0; for(int i=0;i<M;i++) scanf("%s",MAP[i]); for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { if(MAP[i][j]=='.') { fx=i,fy=j; flag=1; break; } } if(flag)break; } bfs(fx,fy); printf("Maximum rope length is %d.\n",bfs(fx,fy)); } return 0; } |