QDC day4

　　图论。

强连通图与弱连通图。

最短路。dij 不支持负权。显然值得一提的是利用斐波那契堆m+nlogn 。

一张边权都是2的整数次幂考虑一下直接结构体维护这个2的整次幂数组但比大小太慢考虑利用数据结构维护。

主席树维护每一位（当然压位也是可以的但却不必要 hash值维护每个区间的值然后就可以快速判断辣。

我们还需要维护一个+1的操作这就涉及到简单的线段树上二分。和区间整体赋值问题。

floyd 设x y z 表示 x y 不经过z 这个点的最短路。经典题目应该是分治一下但是我不太回写，回来写一遍。

spfa 值得一提的是复杂度为nm 这个很容易被卡掉具体卡掉代码如下。

#include <bits/stdc++.h>

using namespace std;

int N = , M = *N-, L = N;

int main()

{

    freopen("in", "w", stdout);

    printf("%d %d %d\n", N*+, M, L);

    for(int i=; i<N; i++) printf("%d %d %d\n", i, i+, );

    printf("%d %d %d\n", N, N*+, );

    for(int i=; i<=N; i++) printf("%d %d %d\n", i, i+N, N-i+);

    for(int i=; i<=N; i++) printf("%d %d %d\n", i+N, i, );

    for(int i=; i<N; i++) printf("%d %d %d\n", i+N, i+N+, );

    for(int i=; i<=L; i++) printf("%d ", i); putchar('\n');

    return ;

}

当然还能在负环上面判断当然dfs套spfa 这个方法有的时候更快一点。当然floyd 也是可以的。

边权递增最短路。

排序边权然后一条一条加入然后每次松弛一下即可。

某个最短路的题目：

有m条边连接两个节点有k条铁路连接1到某个点求最多去掉多少条道路使得 1到任意节点的最短路不变。

这道题

n个点m条边 dij 表示两点之间最短路每个点都有点权求 min{2*dij + aj};

这将等价于 min{dij+d 0 j} 即可。

n 个点 m 条边其中有k 个关键点求 k个关键点之间两两之间最短路的最小值。

咕了。

一张图 A B C 的基地随意选然后求一个点到A B C 的最短路和最小求期望和。

不会咕了。膜改 bfs 一下即可。

巴特西

QDC day4

最新文章

热门文章