1021 Deepest Root (1)

莽夫做题——鄙陋的n次dijkstra

今天基本是玩了一天,熊杰的家针不戳&谢谢xl帮本冒失鬼带回充电器并且还捎来一袋薯片。

题面

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤10​4​​) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N−1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print Error: K components where K is the number of connected components in the graph.

Sample Input 1:

5
1 2
1 3
1 4
2 5

Sample Output 1:

3
4
5

Sample Input 2:

5
1 3
1 4
2 5
3 4

Sample Output 2:

Error: 2 components

(。。。对不起我就是莽夫本夫

题意翻译:给一个图,n个点n-1条边
若这个图是非连通图,则输出非连通块的个数(水)
若这个图是连通图,则这个图是一棵树,输出合适的根节点集合以保证以这些根节点所构成的树深度最大

第一个小任务的解法详见 1013 Battle Over Cities ,DFS、BFS或者并查集都ok,这里不多说。

对于第二个小任务,我的思路是:因为是稀疏图,所以n次dijkstra可以算出每个节点到其最远节点的距离,显然这个最远距离就是树的深度,然后再将这些最远距离做比较就可以求出能使树的深度最大的节点集合。(思路显然没有问题,莽夫们都这么想)
代码如下(没错我之前还写过一个floyd版本的,由于我感觉太傻比就不放出来了):

// 傻逼才用floyd,正常人(莽夫)都用n次Dijkstra的好吧
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define MAXN 10001
#define INFI 10000001
using namespace std;
vector<int> map[MAXN];
int n;

int dijkstra(int c)
{
    int dis[MAXN];
    bool vis[MAXN];

    fill(vis + 1, vis + n + 1, 0);
    fill(dis, dis + n + 1, INFI);

    for (int i = 0; i < map[c].size(); i++)
    {
        dis[map[c][i]] = 1;
    }
    dis[c] = 0;
    vis[c] = true;

    for (int i = 1; i <= n; i++)
    {

        int min = INFI;
        int mini = 0;
        for (int j = 1; j <= n; j++)
        {
            if (vis[j])
            {
                continue;
            }
            else if (dis[j] < min)
            {
                min = dis[j];
                mini = j;
            }
        }
        vis[mini] = true;
        for (int j = 0; j < map[mini].size(); j++)
        {
            if (vis[map[mini][j]])
            {
                continue;
            }
            else
            {
                if (dis[map[mini][j]] > dis[mini] + 1)
                {
                    dis[map[mini][j]] = dis[mini] + 1;
                }
            }
        }
    }
    int max = -1;
    int maxi = 0;
    for (int i = 1; i <= n; i++)
    {
        if (max < dis[i])
        {
            max = dis[i];
            maxi = i;
        }
    }
    return max;
}

void count()
{
    stack<int> s;
    bool vis[MAXN];
    int ans = 0;
    fill(vis + 1, vis + n + 1, 0);

    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
        {
            continue;
        }
        else
        {
            vis[i] = true;
            s.push(i);
            while (!s.empty())
            {
                int c = s.top();
                s.pop();
                for (int j = 0; j < map[c].size(); j++)
                {
                    if (!vis[map[c][j]])
                    {
                        vis[map[c][j]] = true;
                        s.push(map[c][j]);
                    }
                }
            }
            ans++;
        }
    }
    printf("Error: %d components", ans);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        int s, e;
        cin >> s >> e;
        map[s].push_back(e);
        map[e].push_back(s);
    }

    int max = -1;
    vector<int> m;
    for (int i = 1; i <= n; i++)
    {
        int c = dijkstra(i);
        if (c == INFI)
        {
            count();
            return 0;
        }

        if (max < c)
        {
            max = c;
            m.clear();
            m.push_back(i);
        }
        else if (max == c)
        {
            m.push_back(i);
        }
    }
    for (int i = 0; i < m.size(); i++)
    {
        cout << m[i] << endl;
    }

    return 0;
}

结果是有一个点因为超时过不了,一开始我以为我是出现了和1013那题一样的错误(就是在计算非连通块数目的时候对节点重复入栈了),后来经过排查发现并不是。

“万般无奈之下”,嗯,我翻阅了答案书(答案书救我于水火之中),发现我的思路是在是鄙陋至极,好,关于答案书上的解法咱们请听下回分解。

(没错我这次又鸽了大模拟并且明天还要再鸽一次!耶!
btw,希望大家心情都要好一点,emo不可取,难受的时候哭哭鼻子也没关系啦!

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments