2019-10-02

知识点

• 图的存储和遍历
• 最短路
• 最小生成树
• 并查集
• 树上倍增
• 割点，割边，连通分量
• 线段树、树链剖分

NOIP2019 最优贸易

对于邮箱午饭图，做一遍拓扑排序，设$f_i$表示最小点权。

NOIP2010 关押罪犯

维护其中一个监狱。

NOI 2011 食物链

int n, size[MAXN], fa[MAXN];
int find( int x ) {
    return x == fa[x] ? fa[x] = find( fa( x ) );
}
void merge( int u, int v ) {
    if ( size[u] < size[v] ) {
        fa[find( u )] = find[v];
        size[find( u )] += size[find( v )];
    }
    else {
        fa[find( v )] = find[u];
        size[find( v )] += size[find( u )];
    }
}

一种高级并查集。

NOIP2013 火车运输

不在最大生成树上的边没有鸟用。

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/479.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。