题目

构造一个 $n(n\le 20)$ 个点 $m(m\le 60)$ 条边的带权 DAG,使得 $1$ 到 $n$ 恰有 $L$ 条路径,且路径长度恰好为从 $0$ 到 $L - 1$ 的整数。

$2\le L\le 10^6$.

分析

考虑若 $L = 2^k - 1$,则我们显然可以建 $k + 1$ 个点,$i$ 号点到 $i + 1$ 号点连两条边,一条权值为 $0$,一条权值为 $2^{i-1}$.

接下来我们考虑一般的情况,考虑枚举路径长度的卡着 $L$ 最高的若干位,在第 $i$ 位处变为了 $0$(而 $L$ 在对应位的值是 $1$),那么从这位开始往下可以取遍 $[0,2^i)$ 中的整数,即连一条从 $i$ 号点到 $n$ 号点的,权值为 $L$ 抹去这一位以下的所有数后的值的边。

至多建 $3\lfloor \log_2 L\rfloor$ 条边,$\lfloor \log_2 L\rfloor + 1$ 个点,可以通过本题。

代码

int main() { 
    int T = 1; //rd(T);
    while(T--) {
        int n, L; rd(L);
        for(n = 0; 1 << n <= L; ++n); --n;
        printf("%d %d\n", n + 1, 2 * n + __builtin_popcount(L) - 1);
        for(int i = 1; i <= n; ++i) {
            printf("%d %d %d\n", i, i + 1, 0);
            printf("%d %d %d\n", i, i + 1, 1 << (i - 1));
        }
        for(int i = 0; i < n; ++i) if((L >> i) & 1) {
            printf("%d %d %d\n", i + 1, n + 1, L & ~((1 << (i + 1)) - 1));
        }
    } return 0;
}
最后修改:2021 年 02 月 04 日 10 : 39 PM