Domácí kolo

E: Směrovníky

Řešení (Zadání úlohy)

Označíme vzdálenost města V do cíle jako v(V). Pokud změníme směrovník ve městě U tak, aby ukazoval na V, v(U) se změní na v(V) + 1 a vzdálenost všech měst, jejichž trasy do cíle vedli přes U se změní na v(V) + 1 - v(U). Takže nám stačí pro každé město spočítat vzdálenost do cíle a kolik soutěžících přes něj přechází při cestě do cíle. Potom prodloužení cest účastníků při změně směrovníku v U do V bude (v(V) + 1 - v(U)) * s(U), kde s(U) je počet účastníkov přecázejících přes U. Při každé změně zkontrolujeme jestli účastníci nechodí v kruhu. Na to ale stačí chodit po směrovnících postupně z V a zkontrolovat či nenarazíme znovu na V.

Když tento algoritmus provedeme pro každou cestu a vybereme maximum. Algoritmus funguje, ale je pomalý, běží v čase O(MN), kde N je počet měst a M je počet cest.

Počítání vzdáleností a počtu procházejících účastníků zrychlíme pomocí rekurze. Procházíme vrcholy, každý zavolá procházení na ty, které do něj přímo posílají lidi směrovníky. Těm předá svoji vzdálenost (a další vrcholy mají o jedna větší) a na oplátku mu každé město pošle počet účastníků, které jím procházejí. Aktuální město potom vrátí součet účastníků kteří do něj přišli plus ti, kteří v něm bydlí. Tím v lineárním čase spočítáme obě hodnoty.

Poslední co potřebujeme umět je rychle ověřit zda nám změna směrovníku nevytvoří cyklus. Podíváme se na dvě veličiny pro každé město: Kolikáté je toto město v pořadí v kterém jsme do něj v rekurzi vešli (této hodnotě se říká preorder) a jako kolikáté je toto město když jsme z něj z rekurze vyšli (postorder). Do města vždy vejdeme při rekurzi dřív než do měst, které přes něj přecházejí. Preorder je pro takové město vždy menší. Naopak, v těchto "podměstech" vyjdeme z rekurze dříve než v základním město, jeho postorder je větší. Takže pokud otáčíme směrovník v U do V, ověříme že neplatí preorder(U) < preorder(V) and postorder(U) > postorder(V). Tedy v čase O(N) spočítáme vzdálenost, počet procházejících účastníků, preorder a postorder, potom v čase O(M) najdeme maximum přes všechny možné cesty.

Ukázkový program - Pomalé řešení (C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct City
{
    ll parent;
    ll weight;
    vector<City*> children;
};

bool createsCycle(vector<City>& cities, ll a, ll b)
{
    ll u = a;
    while(u != 0)
    {
        if(u == b)
            return true;
        u = cities[u].parent;
    }
    u = b;
    while(u != 0)
    {
        if(u == a)
            return true;
        u = cities[u].parent;
    }
    return false;
}

ll depth(vector<City>& cities, ll a)
{
    ll d = 0;
    for(;a != 0;a = cities[a].parent)
        d++;
    return d;
}

ll subtreeWeight(City& a)
{
    ll result = a.weight;
    for(auto&& child : a.children)
        result += subtreeWeight(*child);
    return result;
}

void doCase()
{
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> edges;
    edges.reserve(m);
    for(ll i = 0; i < m; i++)
    {
        ll u, v;
        cin >> u >> v;
        edges.push_back(make_pair(u, v));
    }
    vector<City> cities(n);
    for(ll i = 1; i < n; i++)
    {
        ll nContestants, direction;
        cin >> nContestants >> direction;
        cities[i].weight = nContestants;
        cities[i].parent = direction;
        cities[direction].children.push_back(&cities[i]);
    }

    pair<ll, ll> bestEdge;
    ll bestImprovement = 0;
    for(auto&& edge : edges)
    {
        if(edge.first == 0 || edge.second == 0)
            continue;
        // najprv jedným smerom potom druhým smerom vyskúšame hranu
        for(ll i = 0; i < 2; i++)
        {
            ll u = edge.first;
            ll v = edge.second;
            if(createsCycle(cities, u, v))
                continue;
            if(cities[u].parent == v) // smerovník sem uŽ smeruje
                continue;
            ll improvement = (depth(cities, v) - depth(cities, u) + 1) * subtreeWeight(cities[u]);
            if(improvement > bestImprovement)
            {
                bestImprovement = improvement;
                bestEdge = edge;
            }
            swap(edge.first, edge.second); // otočíme hranu
        }
    }

    if(bestImprovement > 0)
        cout << bestEdge.first << " " << bestEdge.second << endl;
    else
        cout << 0 << endl;
}

int main()
{
    ll t;
    cin >> t;
    for(ll i = 0; i < t; i++)
        doCase();
}

Ukázkový program - Optimální řešení (C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct City
{
    ll parent;
    ll weight;
    vector<City*> children;
    ll subtreeWeight;
    ll depth;
    ll preorder;
    ll postorder;

    ll traverse(ll depth, ll preorder, ll postorder)
    {
        this->depth = depth;
        this->preorder = preorder;
        preorder++;
        this->subtreeWeight = this->weight;
        for(auto&& child : children)
        {
            preorder = child->traverse(depth + 1, preorder, postorder);
            postorder = child->postorder;
            subtreeWeight += child->subtreeWeight;
        }
        this->postorder = postorder + 1;
        return preorder;
    }
};

bool createsCycle(City& a, City& b)
{
    return (a.preorder >= b.preorder && a.postorder <= b.postorder) ||
        (b.preorder >= a.preorder && b.postorder <= a.postorder);
}

void doCase()
{
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> edges;
    edges.reserve(m);
    for(ll i = 0; i < m; i++)
    {
        ll u, v;
        cin >> u >> v;
        edges.push_back(make_pair(u, v));
    }
    vector<City> cities(n);
    for(ll i = 1; i < n; i++)
    {
        ll nContestants, direction;
        cin >> nContestants >> direction;
        cities[i].weight = nContestants;
        cities[i].parent = direction;
        cities[direction].children.push_back(&cities[i]);
    }

    cities[0].traverse(0, 0, 0);

    pair<ll, ll> bestEdge;
    ll bestImprovement = 0;
    for(auto&& edge : edges)
    {
        if(edge.first == 0 || edge.second == 0)
            continue;
        // najprv jedným smerom potom druhým smerom vyskúšame hranu
        for(ll i = 0; i < 2; i++)
        {
            ll u = edge.first;
            ll v = edge.second;
            if(createsCycle(cities[u], cities[v]))
                continue;
            if(cities[u].parent == v) // smerovník sem už smeruje
                continue;
            ll improvement = (cities[v].depth - cities[u].depth + 1) * cities[u].subtreeWeight;
            if(improvement > bestImprovement)
            {
                bestImprovement = improvement;
                bestEdge = edge;
            }
            swap(edge.first, edge.second); // otočíme hranu
        }
    }

    if(bestImprovement > 0)
        cout << bestEdge.first << " " << bestEdge.second << endl;
    else
        cout << 0 << endl;
}

int main()
{
    ll t;
    cin >> t;
    for(ll i = 0; i < t; i++)
        doCase();
}

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)