DP&图论 DAY 5 上午

  DP&图论  DAY 5  上午

 

 POJ 1125 Stockbroker Grapevine

 有 N 个股票经济人可以互相传递消息,他们之间存在一些单向
的通信路径。现在有一个消息要由某个人开始传递给其他所有
人,问应该由哪一个人来传递,才能在最短时间内让所有人都接
收到消息。

Solution

全局最短路

Floyd

 

 

POJ 1502 MPI Maelstrom

给出 N 个处理器之间传递信息所需时间矩阵的下三角,求信息
从第一个处理器传到其它所有处理器所需时间最大值。

Solution

单源最长路   dij(n m logn)

 n^2 logn

 

 

 

POJ 1511 Invitation Cards

N 个点 M 条边的有向图,询问对于所有 i,从点 1 出发到点 i 并
返回点 1 所需时间最小值。

Solution

# 正向建图 + 单源最短路
# 反向建图 + 单源最短路 ,所以就是把有向边反过来,从点1出发 dij 其实是反向最短路

 

 

 

POJ 1724 ROADS

有 N 个城市和 M 条单向道路,每条道路有长度和收费两个属性。
求在总费用不超过 K 的前提下从城市 1 到城市 N 的最短路。

Solution

Dijkstra,同时维护当前路径总费用,超过费用上限的状态不再转移 

DP&图论  DAY 5  上午

对于每个点拆成k个点,(u,0),(u,1),.......(u,k)

分层图

 DP&图论  DAY 5  上午

 

 

 

 

 POJ 1797 Heavy Transportation

 给出 N 个点 M 条边的无向图,每条边有最大载重。
求从点 1 到点 N 能通过的最大重量。

 Solution

1.二分答案,假设最大载重>=mid,只能通过限重>=mid的边,加到图中,判断连通性

2.最大生成树 krus,判断 1---n 连通性,连通即终止

   从大到小加边,第一次连通1和n那么那条边就是答案

   并查集维护加入前 k 大边时的连通性

3.dijkstra   变种单源最短路,路径长度改为路径边权最小值

   if ( dis[v] < min(dis[u],w) )  dis[v] = min( dis[u] , w )

 

 

 

POJ 1062 昂贵的聘礼 http://poj.org/problem?id=1062 )

PS:注意酋长地位不一定是最高的

 

Solution

 先对于地位升序排列,然后枚举[酋长,酋长+m]这个区间来作为最大的地位  跑区间长度次最短路

 

从原价的超级远点跑dij,然后到点1 

 

1.建图,物品作为点,替代关系作为边,优惠价格是长度

   比如  酋长女儿<------水晶球    权值是优惠价格

   从某物品出发交换至酋长允诺就是一条路径

   不考虑地位限制,从酋长允诺出发求单源最短路即可知道从任意一点出发所需金币

   这是一个反向最短路  反向 dij

2. 枚举地位等级区间,不在地位等级区间内的点不可经过,枚举量 O(N) 
    为了“间接交易”合法,枚举的区间左右端点等级之差<=m

    也就是 max - min <= m  ,为了使得在一个区间内有更大的交易余地,我们设定max-min=m

    然后考虑在这区间内部的都可以交易,不合法的就在图中删掉

    DP&图论  DAY 5  上午

    看数据,m可能很大,但是n小,然后就考虑枚举点作为区间端点

    DP&图论  DAY 5  上午

3.剩下的合法的图跑反向 dij 

 

 

 

 

BZOJ 3040 最短路 *

N 个点, M 条边的有向图,求点 1 到点 N 的最短路(保证存在)。
1 ≤ N ≤ 1000000, 1 ≤ M ≤ 10000000
By lydrainbowcat
边集分为两部分:
# 随机生成
# 输入给出

Solution

1. 采用高效的堆来优化 Dijkstra 算法。
    # 斐波那契堆
    # 配对堆

       dij ,一个大图就凉

       SPFA太小,凉

       dij 用支持修改删除的堆,配对堆

2.用 pq 做,随机生成的数据不要,直接删掉

   https://paste.ubuntu.com/p/Mp2fXMKv8J/

   DP&图论  DAY 5  上午

DP&图论  DAY 5  上午  *d就是只输入不赋值

 

priority_queue  STL实现合并

启发式合并,两个堆,A,B,把较小的堆拆了,放到较大的堆里面

每个点最多产生 logn 次代价

 

 

 

最小生成树算法

DP&图论  DAY 5  上午

Prim

 DP&图论  DAY 5  上午

// Prim

void prim() {
    memset(dis, inf, sizeof dis);
    heap.push(data(1, dis[1] = 0));
    int ans = 0;
    while (!heap.empty()) {
        data t = heap.top(); heap.pop();
        if (dis[t.u] != t.d)continue;
        ans += t.d;
        for (int i = hd[t.u], v, w; i; i = nt[i])
            if (v = to[i], w = vl[i], dis[v] > w)
                heap.push(data(v, dis[v] = w));
    }
}

 DP&图论  DAY 5  上午

 

 

 Kruskal

DP&图论  DAY 5  上午

复杂度卡在排序上

证明依赖于拟阵的知识。 

 

> 拟阵

DP&图论  DAY 5  上午

独立集 

交换性的推论:一个集合的所有极大独立集大小都相同。

                         如果不相同,就交换

 

 

线性相关:向量*常数,加起来,是0向量

拟阵最优化

DP&图论  DAY 5  上午

DP&图论  DAY 5  上午

 

 

 

POJ 1258 Agri-Net

有 N 个村庄,村庄之间形成完全图。现给出邻接矩阵,选择总
长度尽可能小的边将 N 个村庄连通。

 >最小生成树

POJ 2421 Constructing Roads

有 N 个村庄,有一些道路已经存在,现在希望用最少的总长度
将所有村庄连通。

>将已经存在道路设置长度为 0。

 

POJ 2560 Freckles

给出平面上 N 个点,求将所有点连通的最小距离和。

>O(N2) 建边。

 

 

POJ 1789 Truck History

有 N 个编号,每个编号均为 7 位数。两个编号之间的距离定义
为其不同位个数,由一个编号生成另一个编号代价为两个编号的
距离。希望用最小总代价从某一编号开始生成所有编号。

>O(N2) 建边。

  一开始没看明白T,距离就是比较两个编号各位数字,然后计算有几位不同

 

 

BZOJ 1601 灌水

DP&图论  DAY 5  上午

>Solution

DP&图论  DAY 5  上午

 

 

BZOJ 2743 滑雪与时间胶囊

DP&图论  DAY 5  上午

Solution

高度从大到小,边从小到大

能够到达的景点容易通过 DFS 或 BFS 求出。

最优解应当构成树形,所需要的时间即为所有边长度之和。易联想到用最小生成树 Kruskal 算法解决本问题。

如何设置 Kruskal 时边的优先级?如何保证选出的有向边集使得每个点从 1 出发可达?

以到达点高度为第一关键字,边长度为第二关键字。到达点高度高的边优先,同样高时边长度短的优先。 

 

BZOJ 2561 最小生成树 *

DP&图论  DAY 5  上午

(放到晚上)

 

 

 

树上倍增

DP&图论  DAY 5  上午

 

 序列倍增

 DP&图论  DAY 5  上午

 

树上倍增

 DP&图论  DAY 5  上午

f[i][j]表示结点编号

如何求解 u 向上移动 k 步是哪个点?

DP&图论  DAY 5  上午

 

最近公共祖先

DP&图论  DAY 5  上午

 

 DP&图论  DAY 5  上午

 

 Tarjan 支持离线

DFS序+RMQ 支持在线

 树上DFS有回溯操作,每个点被放进的次数就是相邻边数,所以序列长度2n

 记录每个点第一次被放进序列,最后一次放进序列

 对于两个点,A,B,最晚的A,最早的B,卡一个区间,区间内出现过 LCA(A,B),而且不存在比他深的节点,区间深度最小,就是 LCA 

 DP&图论  DAY 5  上午

 

 

向上路径

如何求解从 u 到 v 路径上边权最值?保证 v 是 u 的祖先。

DP&图论  DAY 5  上午

 

 

 树上路径

 DP&图论  DAY 5  上午

如何求解从 u 到 v 路径上的边权和?

将路径拆分为两段向上路径,分别求解其答案再合并。

 

上一篇:【题解】CF545E:Paths and Trees


下一篇:利用 uDig 生成 GeoServer 可用的 SLD 渲染文件