Rikka with Tree

Accepts: 207

Submissions: 815

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：

对于一棵树TT,令F(T,i)F(T,i)为点1到点ii的最短距离（边长是1）. 

两棵树AA和BB是相似的当且仅当他们顶点数相同且对于任意的ii都有F(A,i)=F(B,i)F(A,i)=F(B,i).

两棵树AA和BB是不同的当且仅当他们定点数不同或者存在一个ii使得以1号点为根的时候ii在两棵树中的父亲不同。

一棵树AA是特殊的当且仅当不存在一棵和它不同的树和它相似。

现在勇太想知道一棵树到底是不是特殊的。

当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？

输入描述

数据组数不超过100组。每组数据的第一行一个整数n(2 \leq n \leq 1000)n(2≤n≤1000)。

接下来n-1n−1行。每行两个整数u,v(1 \leq u,v \leq n)u,v(1≤u,v≤n)，代表给定树上的一条边。

输出描述

对于每一组数据，如果给定树是特殊的输出"YES"否则输出"NO"。

输入样例

输出样例

YES

NO

Hint

对于第二组数据下面这棵树和它相似。

4

1 2

1 4

3 4

官方题解：显然一棵树是独特的当且仅当任意处于每一个深度的点数是"1 1 1 1 ... 1 1 x"。所以直接DFS一下求出每一个点到根的距离然后判断一下就好了。

看到从1到各个点的最短距离，就想到Dijkstra了。用Dijkstra求每个点的最短路径，之后在对最大值做判断即可。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

const int MAX = 0xfffffff;

int edge[1005][1005];

int vist[1005], minidis[1005];

int num;

void init()

{

    int i, j;

    memset(vist, 0, sizeof(vist));

    for (i = 1; i <= num; i++)

    {

        for (j = 1; j <= num; j++)

        {

            if (j == i)

                edge[i][j] = 0;

            else

                edge[i][j] = -1;

        }

    }

    for (i = 1; i <= num; i++)

    {

        vist[i] = 0;

        minidis[i] = MAX;

    }

}

void dijkstra(int i)

{

    int j, k;

    int position = i;

    vist[position] = 1;

    minidis[position] = 0;

    for (j = 1; j <= num - 1; j++)//一共要添加进num-1个点

    {

        for (k = 1; k <= num; k++)

        {

            if (vist[k] == 0 && edge[position][k] != -1 && minidis[position] + edge[position][k] < minidis[k])//新填入的点更新minidis

            {

                minidis[k] = minidis[position] + edge[position][k];

            }

        }

        int min_value = MAX, min_pos;

        for (k = 1; k <= num; k++)

        {

            if (vist[k] == 0 && minidis[k]<min_value)//比较出最小的那一个作为新添入的店

            {

                min_value = minidis[k];

                min_pos = k;

            }

        }

        vist[min_pos] = 1;

        position = min_pos;

    }

}

int main()

{

    //freopen("i.txt", "r", stdin);

    //freopen("o.txt", "w", stdout);

    int i,j,temp1,temp2,max_v;

    while (scanf("%d", &num)!=EOF)

    {

        init();

        for (i = 1; i <= num - 1; i++)

        {

            scanf("%d%d", &temp1, &temp2);

            edge[temp1][temp2] = 1;

            edge[temp2][temp1] = 1;

        }

        dijkstra(1);

        bool flag = true;

		max_v=-1;

		for (i = 2; i <= num ; i++)

		{

			max_v=max(max_v,minidis[i]);

		}

        for (i = 2; i <= num ; i++)

        {

            for (j = i + 1; j <= num; j++)

            {

                if (minidis[i] == minidis[j]&&minidis[i] != max_v)

                    flag = false;

            }

        }

        if (flag)

            cout << "YES" << endl;

        else

            cout << "NO" << endl;

    }

    return 0;

}

秒客网

HDU 5423:Rikka with Tree Dijkstra算法

Rikka with Tree

相关文章