Турнир за Купата на Декана - 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;
}
Автор: Антон Димитров
обратно към текущ брой
|