首页 > 搜索 > BFS搜索 > HDU 4514-湫湫系列故事――设计风景线-图-[解题报告]HOJ
2015
07-17

HDU 4514-湫湫系列故事――设计风景线-图-[解题报告]HOJ

湫湫系列故事――设计风景线

问题描述 :

  随着杭州西湖的知名度的进一步提升,园林规划专家湫湫希望设计出一条新的经典观光线路,根据老板马小腾的指示,新的风景线最好能建成环形,如果没有条件建成环形,那就建的越长越好。
  现在已经勘探确定了n个位置可以用来建设,在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线?如果不能,风景线最长能够达到多少?
  其中,可以兴建的路线均是双向的,他们之间的长度均大于0。

输入:

  测试数据有多组,每组测试数据的第一行有两个数字n, m,其含义参见题目描述;
  接下去m行,每行3个数字u v w,分别代表这条线路的起点,终点和长度。

  [Technical Specification]
  1. n<=100000
  2. m <= 1000000
  3. 1<= u, v <= n
  4. w <= 1000

输出:

  测试数据有多组,每组测试数据的第一行有两个数字n, m,其含义参见题目描述;
  接下去m行,每行3个数字u v w,分别代表这条线路的起点,终点和长度。

  [Technical Specification]
  1. n<=100000
  2. m <= 1000000
  3. 1<= u, v <= n
  4. w <= 1000

样例输入:

3 3
1 2 1
2 3 1
3 1 1

样例输出:

YES

题目链接:Click here~~

题意:

给一个无向图,若有环输出YES,若无环,则是森林,输出 max { 树的直径 }。(树中最长的简单路)

解题思路:

早早地就搜了几篇文章,还下载了个PPT。研究了半天,终于搞懂后,搜了好多判环和求树的直径的代码,都和我要写的方法不一样。

纠结了好久不敢写,后来脑子疼了,打算乱写一通试试,结果随便调了调竟然就过了。(是太不相信自己了么?

首先,无向图判环,想到用 dfs,但是要记录前驱节点。(但我百度半天没发现这么写的,所以一直不敢肯定自己是对的。。。

然后,如何求树的直径呢?

随便找一个点u ,找到距离 u 最远的点 v。

然后再从 v 出发,找距离 v 最远的点 w,路径(v -> w)就是树的直径。

证明:首先,v 一定是直径的一端。

           a) 如果 u 是直径的一端,那么 v 显然是直径的另一端,结论成立。

           b) 如果 u 不是直径的一端,那么路径(u->v)一定与直径交于一点 p,且(p->v)一定是直径的一部分,推出 v 是直径的一端,结论成立。

            
         1> 为什么一定存在交点 p?

 
                               如果不存在交点 p ,由于树是连通的,那么加若干边使得直径经过(u->v)上的一点 p,直径不会变得更短。

 
                    2>为什么(p->v)一定是直径的一部分。

 
                               如果不是,(u->v)就不是从 u 到 v 最长的路径。

于是我成功的将判环和求直径用一个 dfs 实现了,233333333。

既然是树,我不明白为什么大家都要去用 bfs 来求路径长度。。。大概是防止RE)


#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 1e5+3;

struct Vertex
{
    int head;
}V[N];

struct Edge
{
    int v,w,next;
}E[N*10*2];

bool vis[N],tmpv[N];

int top,d[N];

void init()
{
    top = 0;
    memset(V,-1,sizeof(V));
}

void addEdge(int u,int v,int w)
{
    E[top].v = v;
    E[top].w = w;
    E[top].next = V[u].head;
    V[u].head = top++;
}

bool dfs(int pre,int u)
{
    vis[u] = true;
    for(int i=V[u].head;~i;i=E[i].next)
    {
        int v = E[i].v;
        if(v == pre)
            continue;
        if(vis[v])
            return false;
        d[v] = d[u] + E[i].w;
        if(!dfs(u,v))
            return false;
    }
    return true;
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        while(m--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addEdge(u,v,w);
            addEdge(v,u,w);
        }
        int ans = 0;
        bool yes = false;
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            if(vis[i])
                continue;
            memset(d,0,sizeof(d));
            if(!dfs(0,i))
            {
                yes = true;
                break;
            }
            int u = max_element(d+1,d+1+n) - d;
            memcpy(tmpv,vis,sizeof(vis));
            memset(vis,false,sizeof(vis));
            memset(d,0,sizeof(d));
            dfs(0,u);
            ans = max(ans,*max_element(d+1,d+1+n));
            memcpy(vis,tmpv,sizeof(vis));
        }
        if(yes)
            puts("YES");
        else
            printf("%d\n",ans);
    }
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dgq8211/article/details/8752927


, ,