Текущ брой на Списание ИнфоМан
 


Турнир за Купата на Декана - 2005, Задача B

Уловието на задачата може да прочетете тук.

Решение

Център в дърво е такъв връх, за който разстоянието до най-отдалеченият му връх е минимално. Разстоянието от един такъв център до най-отдалечения за него връх е търсеният отговор.

Ще покажем, че центровете в едно дърво лежат на пътя между двата най-отдалечени върха в дървото. Нека най-отдалечените върхове са P и Q. Нека разстоянието между P и Q е L. Нека X е върха от пътя между P и Q, който е на разстояние r от P. r е най-малкото цяло число, което е по-голямо или равно на L/2. Нека има връх Y, който е център и не е от пътя между P и Q. Тогава единият от двата върха P или Q е на разстояние r+1 или повече от Y. Нека съществува връх Z, който е на разстояние r+2 от X. В такъв случай най-дългият път в дървото няма да е между P и Q. Ще съществува път с по-голяма дължина между Z и някой от върховете P или Q. Това води до противоречие с твърдението, че най-дългият път в дървото е между P и Q. От тук следва, че не съществува връх, който е на разстояние от X, което е по-голямо от r+1. Следователно избраният връх X е център на дървото.

Остава да се намери най-дългият път в дървото. Отговора на поставената задача ще е числото r.

Нека най-дългият път в дървото е между върховете E и F. За всеки връх в дървото най-отдалеченият му връх е някой от двата E или F. Нека приемем, че е някой друг, например D. Излиза че пътя между D и някой от двата върха E или F е по-дълъг от пътя между E и F. Това е в противоречие с допускането. Сега това твърдение може да се използва, за да се намери най-дългият път в дървото.

За да се намери този най-дълъг път се избира един произволен връх в дървото и се намира най-отдалечения за него F. След това се намира най-отдалечения връх от F. Нека това е E. Пътят между върховете E и F е най-дългият в дървото. Най-отдалеченият връх може да се намери с някакво обхождане – в дълбочина или в ширина.

Сложността на описаното решението е O(N), където N e броят на върховете в дървото.

Примерна реализация


#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

#define MAXN        10004

int n;
vector<int> nasl[MAXN];
int lev[MAXN];
int vis[MAXN];
int node1,node2;
queue<int> tail;
int ans;

ifstream fin(stdin);

int BFS(int node)
{
    int i;
    int curn,nn;
    int max,mind;

    memset(vis,0,sizeof(vis));

    vis[node] = 1;
    lev[node] = 0;
    max = 0;
    mind = node;

    tail.push(node);

    while(!tail.empty())
    {
        curn = tail.front();
        tail.pop();
        for(i=0;i<nasl[curn].size();i++)
        {
            nn = nasl[curn][i];
            if(!vis[nn])
            {
                vis[nn] = 1;
                tail.push(nn);
                lev[nn] = lev[curn]+1;
                if(lev[nn]>max)
                {
                    max = lev[nn];
                    mind = nn;
                }
            }
        }
    }

    return mind;
}

int main()
{
    int i;
    int a,b;

    fin >> n;
    
    for(i=1;i<n;i++)
    {
        fin >> a >> b;
        nasl[a].push_back(b);
        nasl[b].push_back(a);
    }

    node1 = BFS(1);
    node2 = BFS(node1);

    ans = lev[node2]/2;
    if(lev[node2]%2) ans++;

    cout << ans << endl;

    return 0;
}

Автор: Антон Димитров


обратно към текущ брой