代码

/* Optimal routing-table compression -- exact DP.
 *
 * The address field is network order, so the numeric address is bswap32(addr).
 * Build the prefix trie of the entries (sorted by (bswap32(addr), len), which is
 * exactly DFS preorder) and select a minimum subset of the entries that keeps the
 * longest-prefix-match function f unchanged.
 *
 * X_v = v's nexthop, p(v) = X_parent(v) (what v inherits in the input),
 * covered(v) = v's range is fully covered by its children's ranges.
 *
 *   S(v)    = sum over children c of nat(c),     nat(v) = f(v, p(v))
 *   emit(v) = 1 + S(v)
 *   f(v,I)  = (I == X_v) ? S(v)                                  // v may be skipped
 *           : min(emit(v), covered(v) ? sum_c f(c,I) : INF)      // v's own region
 *                                                                // needs value X_v
 *
 * Only a strict ancestor's nexthop can ever be inherited and there are at most
 * depth many distinct ones, so a single DFS that carries the ancestor values (with
 * one running sum per carried value) evaluates the whole DP in O(n * depth).  A
 * second top-down pass reconstructs an optimal set of entries.
 */
#include "routecomp.h"
#include <stdlib.h>
#include <string.h>

typedef unsigned u32;
typedef unsigned long long u64;

#define MAXD 40
#define BIGV (1 << 26)

static RoutingTableEntry *E;
static int nE;
static int *fc, *ns, *par_, *Sarr;
static u64 *wR, *eR;
static u32 *bR;
static unsigned char *covR;
static RoutingTableEntry *OUT;
static int OUTC;

static inline u32 kof(u32 a) { return a; }
static inline u64 widthOf(int len) { return len >= 32 ? 1ULL : (1ULL << (32 - len)); }
static inline u32 baseOf(u32 k, int len) {
    if (len <= 0) return 0u;
    if (len >= 32) return k;
    return k & ~((u32)((1ULL << (32 - len)) - 1));
}

static int evalF(int v, u32 I) {
    int S = Sarr[v];
    if (I == E[v].nexthop) return S;
    int emit = S + 1;
    if (!covR[v]) return emit;
    int acc = 0;
    for (int c = fc[v]; c != -1; c = ns[c]) {
        acc += evalF(c, I);
        if (acc >= emit) return emit;
    }
    return acc < emit ? acc : emit;
}

static void pass1(int v, const u32 *vals, int nv, int *out) {
    u32 vals2[MAXD];
    int nv2 = nv;
    for (int i = 0; i < nv; i++) vals2[i] = vals[i];
    u32 xv = E[v].nexthop;
    int xi = -1;
    for (int i = 0; i < nv; i++) if (vals[i] == xv) { xi = i; break; }
    if (xi < 0) { xi = nv2; vals2[nv2++] = xv; }
    int acc[MAXD];
    for (int i = 0; i < nv2; i++) acc[i] = 0;
    int sumS = 0;
    u64 covw = 0;
    int has = 0;
    for (int c = fc[v]; c != -1; c = ns[c]) {
        int cout[MAXD];
        pass1(c, vals2, nv2, cout);
        has = 1;
        sumS += cout[xi];
        if (sumS > BIGV) sumS = BIGV;
        for (int i = 0; i < nv2; i++) { acc[i] += cout[i]; if (acc[i] > BIGV) acc[i] = BIGV; }
        covw += wR[c];
        if (covw > wR[v]) covw = wR[v] + 1;
    }
    Sarr[v] = sumS;
    covR[v] = (unsigned char)(has && covw == wR[v]);
    for (int i = 0; i < nv; i++) {
        if (vals[i] == xv) out[i] = sumS;
        else if (!covR[v]) out[i] = sumS + 1;
        else { int a = acc[i], e2 = sumS + 1; out[i] = a < e2 ? a : e2; }
    }
}

static void collect(int v, u32 I) {
    u32 xv = E[v].nexthop;
    int emit;
    if (I == xv) emit = 0;
    else {
        int e2 = Sarr[v] + 1;
        if (!covR[v]) emit = 1;
        else {
            int acc = 0;
            for (int c = fc[v]; c != -1; c = ns[c]) { acc += evalF(c, I); if (acc >= e2) break; }
            emit = (acc >= e2) ? 1 : 0;
        }
    }
    if (emit) {
        RoutingTableEntry *o = &OUT[OUTC++];
        o->addr = E[v].addr;
        o->len = E[v].len;
        o->pad[0] = o->pad[1] = o->pad[2] = 0;
        o->nexthop = xv;
    }
    for (int c = fc[v]; c != -1; c = ns[c]) collect(c, emit ? xv : I);
}

void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
    *tbl_comp = 0; *n_comp = 0;
    if (n <= 0) return;
    E = (RoutingTableEntry *)malloc((size_t)n * sizeof(RoutingTableEntry));
    fc = (int *)malloc((size_t)n * sizeof(int));
    ns = (int *)malloc((size_t)n * sizeof(int));
    par_ = (int *)malloc((size_t)n * sizeof(int));
    Sarr = (int *)malloc((size_t)n * sizeof(int));
    wR = (u64 *)malloc((size_t)n * sizeof(u64));
    eR = (u64 *)malloc((size_t)n * sizeof(u64));
    bR = (u32 *)malloc((size_t)n * sizeof(u32));
    covR = (unsigned char *)malloc((size_t)n);
    RoutingTableEntry *tmp = (RoutingTableEntry *)malloc((size_t)n * sizeof(RoutingTableEntry));
    int *stk = (int *)malloc((size_t)(n + 2) * sizeof(int));
    if (!E || !fc || !ns || !par_ || !Sarr || !wR || !eR || !bR || !covR || !tmp || !stk) return;
    memcpy(E, tbl, (size_t)n * sizeof(RoutingTableEntry));

    /* stable sort by (len, key): counting sort on len then 4 LSD radix passes */
    {
        static u32 cl[40];
        memset(cl, 0, sizeof(cl));
        for (int i = 0; i < n; i++) { int L = E[i].len; if (L > 32) L = 32; cl[L]++; }
        { u32 s = 0; for (int i = 0; i < 40; i++) { u32 c = cl[i]; cl[i] = s; s += c; } }
        for (int i = 0; i < n; i++) { int L = E[i].len; if (L > 32) L = 32; tmp[cl[L]++] = E[i]; }
        RoutingTableEntry *src = tmp, *dst = E;
        for (int pass = 0; pass < 4; pass++) {
            int sh = pass << 3;
            static u32 cnt[256];
            memset(cnt, 0, sizeof(cnt));
            for (int i = 0; i < n; i++) cnt[(kof(src[i].addr) >> sh) & 255u]++;
            u32 s = 0;
            for (int i = 0; i < 256; i++) { u32 c = cnt[i]; cnt[i] = s; s += c; }
            for (int i = 0; i < n; i++) { u32 a = kof(src[i].addr); dst[cnt[(a >> sh) & 255u]++] = src[i]; }
            RoutingTableEntry *t = src; src = dst; dst = t;
        }
        if (src != E) memcpy(E, src, (size_t)n * sizeof(RoutingTableEntry));
    }

    /* dedupe (addr,len) keeping the first occurrence (LPM tie-break) */
    {
        int m = 0;
        for (int i = 0; i < n; i++) {
            if (m > 0 && E[m - 1].addr == E[i].addr && E[m - 1].len == E[i].len) continue;
            E[m++] = E[i];
        }
        nE = m;
    }

    /* trie links */
    {
        int sp = 0;
        for (int i = 0; i < nE; i++) {
            u32 k = kof(E[i].addr);
            int L = (int)E[i].len; if (L > 32) L = 32;
            u32 b = baseOf(k, L);
            u64 w = widthOf(L);
            bR[i] = b; wR[i] = w; eR[i] = (u64)b + w;
            fc[i] = -1; ns[i] = -1;
            while (sp > 0 && eR[stk[sp - 1]] <= (u64)b) sp--;
            par_[i] = (sp > 0) ? stk[sp - 1] : -1;
            if (sp > 0) { int p = stk[sp - 1]; ns[i] = fc[p]; fc[p] = i; }
            stk[sp++] = i;
        }
    }

    /* pass 1: forest roots inherit 0 */
    {
        u32 v0[1]; v0[0] = 0u;
        int out0[1];
        for (int i = 0; i < nE; i++) if (par_[i] == -1) pass1(i, v0, 1, out0);
    }

    /* pass 2: rebuild an optimal table */
    OUT = (RoutingTableEntry *)malloc((size_t)nE * sizeof(RoutingTableEntry) + 16);
    if (!OUT) return;
    OUTC = 0;
    for (int i = 0; i < nE; i++) if (par_[i] == -1) collect(i, 0u);
    *tbl_comp = OUT;
    *n_comp = OUTC;

    free(E); free(fc); free(ns); free(par_); free(Sarr);
    free(wR); free(eR); free(bR); free(covR); free(tmp); free(stk);
}

评测结果