M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

求树的直径

              树的直径是指树的最长简单路。求法: 两遍BFS :先任选一个起点BFS找到最长路的终点,再从终点进行BFS,则第二次BFS找到的最长路即为树的直径;
              原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
              证明: 1) 如果u 是直径上的点,则v显然是直径的终点(因为如果v不是的话,则必定存在另一个点w使得u到w的距离更长,则于BFS找到了v矛盾)
                      2) 如果u不是直径上的点,则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
                       所以v一定是直径的一个端点,所以从v进行BFS得到的一定是直径长度

              相关题目有TOJ1056,TOJ3517.

TOJ 1056(Labyrinth):
        大意是一个由‘#’和'.'构成的迷宫,'.'表示可行,‘#’表示不可行,问可行的最长的路的长度是多少。

#include <cstdio>
#include 
<cstring>
#include 
<queue>
#define M 1002

using namespace std;

int r,c;
char map[M][M];
bool flag[M][M];
int move[4][2]={-1,0,1,0,0,-1,0,1};                                               // 分别表示上下左右
int maxt;
struct Node{
        
int x,y,num;
};
Node ans;
bool legal(int x,int y){                                                                   //判断该点是否越界及是否可走
        if(x >=0 && x < r && y>=0 && y < c &&map[x][y]=='.'return true;
        
return false;
}
void bfs(Node start){
        memset(flag,
false,sizeof(flag));                                               //初始所有点标记为false
        flag[start.x][start.y] = true;                                                    //起点标记为true
        queue<Node>f;
        
while(!f.empty()) f.pop();                                                       //清空创建的队列
        Node m,n,tep;
        
int tx,ty,xx,yy;
        
int i,j,k,num;
        f.push(start);
        
while(!f.empty()){                                                                   //如果队列不为空
                m = f.front();                                                                   //取出队首元素
                tx = m.x; ty = m.y; num = m.num;
                
if(num > maxt){                                                              //如果该元素的长度大于maxt,更新maxt
                        maxt = num;
                        ans 
= m;
                }
                
for(i = 0;i < 4; i++){                                                       //以m为起点向4个方向BFS
                        xx = tx + move[i][0];
                        yy 
= ty + move[i][1];
                        
if(!flag[xx][yy] && legal(xx,yy)){
                                flag[xx][yy] 
= true;
                                tep.x 
= xx;
                                tep.y 
= yy;
                                tep.num 
= num + 1;
                                f.push(tep);
                                
if(num+1>maxt){                                            //如果有更大的则更新
                                        maxt = num + 1;
                                        ans 
= tep;
                                }
                        }
                }
                f.pop();                                                                              
//弹出队首元素
        } 
}
int main(){
        
int i,j,T;
        Node start,end;
        
bool mark;
        scanf(
"%d",&T);
        
while(T--){
                scanf(
"%d%d",&c,&r);
                mark 
= false; maxt = -1;
                
for(i = 0;i < r; i++)
                        scanf(
"%s",map[i]);
                
for(i = 0;i < r; i++){
                        
for(j = 0;j < c; j++){
                                
if(map[i][j]=='.'){                                                     //任选一点BFS
                                        start.x = i;
                                        start.y 
= j;
                                        start.num 
= 0;
                                        bfs(start);
                                        mark 
= true;
                                        
break;
                                }
                        }
                        
if(mark) break;
                }
                maxt 
= -1;ans.num = 0;                                                           //此时ans一定是直径的端点,将它设为起点
                bfs(ans);                                                                                    //进行第二次BFS
                printf("Maximum rope length is %d.\n",maxt);
        }
}


TOJ3517(The longest athletic track):
          题目给出了一棵生成树,问这棵生成树最长的路的长度是多少。

#include<iostream>
#include
<queue>
#define INF 999999
#define M 2002
using namespace std;
int n;
int maxx;
int map[M][M],sum[M];
bool flag[M];
int bfs(int begin){
            queue
<int>f;
           
int i,m,k,key;
            maxx
=0;
            memset(flag,
false,sizeof(flag));
            f.push(begin);
           
while(!f.empty()){
                        k
=f.front();
                        
for(i=1;i<=n;i++){
                                
if(map[k][i]!=INF&&!flag[i]){
                                            flag[i]
=true;
                                            f.push(i);
                                            sum[i]
=sum[k]+map[k][i];
                                            
if(sum[i]>maxx) { maxx=sum[i];key=i; }
                                 }
                         }
                         f.pop();
            }
           
return key;
}
int main()
{
           
int i,j,k,dis,key,cas;
            scanf(
"%d",&cas);
           
while(cas--){
                         scanf(
"%d",&n);
                        
for(i=1;i<n;i++)
                                  
for(j=i+1;j<=n;j++)
                                            map[i][j]
=map[j][i]=INF;
                        
for(i=1;i<n;i++){
                                   scanf(
"%d%d%d",&j,&k,&dis);
                                   map[j][k]
=map[k][j]=dis;
                         }
                         sum[
1]=0;
                         key
=bfs(1);
                         sum[key]
=0;
                         key
=bfs(key);
                         printf(
"%d\n",maxx);
             }
    
//system("pause");
}





posted on 2010-07-08 01:14 M.J 阅读(2572) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理