POJ1985+POJ2631 求一棵树的直径

以你之姓@ 2022-08-22 03:56 179阅读 0赞

这两个题目都是求解一棵树的直径，也就是书里面的最长的一段距离。

树的直径是指树的最长简单路。求法: 两遍BFS（dfs） :先任选一个起点BFS（dfs）找到最长路的终点，再从终点进行BFS（dfs），则第二次BFS（dfs）找到的最长路即为树的直径。

证明网上有很多，在此就不写了。

下面分别列出两种方法，一种是bfs，一种是dfs。

//POJ 1985
    
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N = 50000;
    struct Node
    {
    	int to,cap;
    };
    vector<Node> v[N];
    int vis[N],dis[N];
    int ans;
    
    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;
    		}
    		for(int i=0;i<v[f].size();i++)
    		{
    			Node tmp = v[f][i];
    			if(vis[tmp.to]==0)
    			{
    				vis[tmp.to]=1;
    				dis[tmp.to] = dis[f] + tmp.cap;
    				q.push(tmp.to);
    			}
    		}
    	}
    	return point;
    }
    int main()
    {
    	int n,m;
    	while(~scanf("%d%d",&n,&m))
    	{
    		for(int i=0;i<=n;i++)
    			v[i].clear();
    		for(int i=0;i<m;i++)
    		{
    			int x,y,z;
    			char c;
    			scanf("%d %d %d %c",&x,&y,&z,&c);
    			v[x].push_back((Node){y,z});
    			v[y].push_back((Node){x,z});
    		}
    		ans = 0;
    		int point = BFS(1);
    		ans = 0;
    		BFS(point);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

//POJ2631
    
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    int const maxn = 100005;
    struct edge
    {
    	int v,next,val;
    }e[maxn];
    bool vis[maxn];
    int n,k,ans,point;
    int head[maxn];
    //head[i]是以点i为起点的链表头部
    
    void addedge(int a,int b,int w)
    {//向图中加边的算法，注意加上的是有向边
    	e[k].v=a;
    	e[k].val=w;
    	e[k].next=head[b];
    	head[b]=k++;
    }
    
    void dfs(int u,int s)
    {
    	vis[u]=1;
    	if(s>ans)
    	{
    		ans=s;
    		point=u;
    	}
    	for(int i=head[u];i>0;i=e[i].next)
    	{
    		int v=e[i].v;
    		if(vis[v]) continue;
    		dfs(v,s+e[i].val);
    	}
    }
    
    int main()
    {
    	int a,b,w;
    	k = 1 ;
    	memset(head,0,sizeof(head));
    	while(cin>>a>>b>>w)
    	{
    		addedge(a,b,w);
    		addedge(b,a,w);
    	}
    
    	ans=0;
    	memset(vis,0,sizeof(vis));
    	dfs(1,0);
    
    	ans=0;
    	memset(vis,0,sizeof(vis));
    	dfs(point,0);
    
    	cout<<ans<<endl;
    
    	return 0;
    }