Arbre de Flux Équilibré#12237

Arbre de Flux Équilibré (Corrigé)

Auteur du problème :	Imran AKKI
Préparé par :	Imran AKKI
Édité par :	Hasan Saleh (MathModel)

Solution Un glouton en un seul passage par élimination des feuilles : garder $rem [u] = b [u]$ \text{rem}[u]=b[u] (la différence sortant-entrant que le sommet doit encore obtenir), mettre toutes les feuilles dans une file, et retirer de façon répétée toute feuille $u$ avec son unique arête inutilisée $e = (u, p)$ e=(u,p). Quand $u$ n'a plus que cette arête, la contribution de $e$ pour $u$ doit être $+ 1$ (si $u \to p$ u \rightarrow p) ou $- 1$ (si $p \to u$ p \rightarrow u), donc $rem [u]$ doit être $+ 1$ ou $- 1$ ; orienter $e$ en conséquence, la marquer utilisée, retirer $u$ (décrémenter les degrés), et propager l'effet au voisin par $rem [p] = rem [p] + rem [u]$ \text{rem}[p]=\text{rem}[p]+\text{rem}[u].

Si à un moment une feuille $u$ a $rem [u]$ n'appartenant pas à ${+ 1, - 1}$ , alors on renvoie NO.

Continuer jusqu'à ce que toutes les arêtes soient orientées (alors YES) ou qu'une contradiction apparaisse. Cela est correct car toute orientation globale valide impose le même choix forcé lorsqu'un sommet devient une feuille (une arête vers une feuille ne peut donner que $\pm 1$ ), donc notre glouton correspond à toute solution et, par induction sur le nombre de sommets, la reconstruit si elle existe ; inversement, si l'algorithme échoue sur une feuille, aucune orientation globale ne peut satisfaire la valeur requise restante de cette feuille.

La complexité totale est $O (n)$ .

// Auteur : Imran AKKI (imranakki)
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lp(i, a, n) for (ll i = a; i < n; i++)
#define MAXN 1000005
#define MOD (ll)(1e9 + 7)
using namespace std;

void solve()
{
    ll n; cin >> n;
    vector<ll> b(n);
    for(auto &e:b) cin >> e;

    vector<vector<ll>> adj(n);
    for(ll i = 0; i < n - 1; i++) {
        ll u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<ll> deg(n, 0);
    queue<ll> q;
    for(ll i = 0; i < n; i++) {
        deg[i] = adj[i].size();
        if(deg[i] == 1) q.push(i);
    }

    vector<pair<ll, ll>> ans;
    vector<bool> vis(n, 0);
    while(!q.empty()) {
        ll u = q.front(); q.pop();
        if(vis[u] || deg[u] != 1) continue;

        if(b[u] != 1 && b[u] != -1) {
            cout << "NO\n";
            return;
        }

        ll p = -1;
        for(auto v: adj[u]) {
            if(!vis[v]){
                p = v;
                break;
            }
        }

        bool u_to_p = (b[u] == 1);
        if(u_to_p){
            ans.push_back({u, p});
            b[p]++;
        }else{
            ans.push_back({p, u});
            b[p]--;
        }

        vis[u] = 1;
        deg[p]--;
        if(deg[p] == 1) {
            q.push(p);
        }
        deg[u] = 0;
    }
    if((ll)ans.size() != n - 1) {
        cout << "NO\n";
    }else{
        cout << "YES\n";
        for(auto &e: ans) cout << e.first + 1 << " " << e.second + 1 << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

C++

Complexité : $O (n)$