树的直径学习小记 Poj 1985 Cow Marathon+Poj 2631 Roads in the North

分手后的思念是犯贱 2022-08-27 03:53 13阅读 0赞

1. 树上面求最长路简单路(无环). 就是树的直径问题.  
2. 树的直径问题经典解法：两遍BFS

> (1). 一开始任取一个点u进行搜索，查找出距离点u最远距离的点v和长度.

> (2). 第二次BFS则从第一次中的点v找出距离点v最远距离的点的路径长度.

3. 解法证明:  
(1). 情况1: u在最长路上, 那么v一定是最长路的一端.

> 反证法: v不是在最长路的一端, 即有一个v1使得(u->v1)是最长路的一部分,

> 就有: dist(u->v1) > dist(u->v); 矛盾.

> 即: v在最长路的一端. (第二次BFS就可以找出距离v最远的点的长度.)

(2). 情况2: u不再最长路上, 则有点u到点v的路与最长路一定有一个交点c.

> 并且(c->v)与最长路的后半段是重合的. 即v一定是最长路的一端.

**Poj 1985 Cow Marathon**

题意：给出各个农场之间的距离,问两个农场之间的最长距离是多少。图中不存在环。

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=80005;
    
    struct Node
    {
    	int v,w;
    	int next;
    }edges[N];
    
    int n,m,e,maxlenth;
    int head[N],dis[N];
    bool vis[N];
    int point_u;
    
    void Add (int u,int v,int w)
    {
    	edges[e].v=v;
    	edges[e].w=w;
    	edges[e].next=head[u];
    	head[u]=e++;
    }
    
    int BFS (int u)
    {
    	memset(vis,false,sizeof(vis));
    	memset(dis,0,sizeof(dis));
    	queue<int> Q;
    	Q.push(u);
    	vis[u] = true;
    	while (!Q.empty())
    	{
    		int s=Q.front();
    		Q.pop();
    		for (int i=head[s];i!=-1;i=edges[i].next)
    		{
    			int v=edges[i].v;
    			if (vis[v]==false)
    			{
    				dis[v]=dis[s]+edges[i].w;
    				Q.push(v);
    				vis[v]=true;
    				if (dis[v]>maxlenth)
    				{
    					maxlenth=dis[v];
    					point_u=v;
    				}
    			}
    		}
    	}
    	return maxlenth;
    }
    
    int main ()
    {
    	while (~scanf("%d%d",&n,&m))
    	{
    		memset(head,-1,sizeof(head));
    		int u,v,w;
    		maxlenth=0;
    		e=0;
    		for (int i=1;i<=m;i++)
    		{
    			scanf("%d%d%d%*s",&u,&v,&w);
    			Add(u,v,w);
    			Add(v,u,w);
    		}
    		BFS(1);
    		printf("%d\n",BFS(point_u));
    	}
    	return 0;
    }

**Poj 2631 Roads in the North**

题意：给出树的两节点之间的边长,求最长路径。

本题输入比较纠结，一开始不告诉有多少节点多少条边，而是一直读到文件结束

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=80005;
    
    struct Node
    {
    	int v,w;
    	int next;
    }edges[N];
    
    int e,maxlenth;
    int head[N],dis[N];
    bool vis[N];
    int point_u;
    
    void Add (int u,int v,int w)
    {
    	edges[e].v=v;
    	edges[e].w=w;
    	edges[e].next=head[u];
    	head[u]=e++;
    }
    
    int BFS (int u)
    {
    	memset(vis,false,sizeof(vis));
    	memset(dis,0,sizeof(dis));
    	queue<int> Q;
    	Q.push(u);
    	vis[u] = true;
    	while (!Q.empty())
    	{
    		int s=Q.front();
    		Q.pop();
    		for (int i=head[s];i!=-1;i=edges[i].next)
    		{
    			int v=edges[i].v;
    			if (vis[v]==false)
    			{
    				dis[v]=dis[s]+edges[i].w;
    				Q.push(v);
    				vis[v]=true;
    				if (dis[v]>maxlenth)
    				{
    					maxlenth=dis[v];
    					point_u=v;
    				}
    			}
    		}
    	}
    	return maxlenth;
    }
    
    int main ()
    {
        memset(head,-1,sizeof(head));
        int u,v,w;
        maxlenth=0;
        e=0;
    	while (~scanf("%d%d%d",&u,&v,&w))
    	{
            Add(u,v,w);
            Add(v,u,w);
        }
        BFS(1);
        printf("%d\n",BFS(point_u));
    	return 0;
    }