正睿OI2019成都站集训Day2

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 火车运输

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

Last modification:October 7th, 2019 at 02:15 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment