刷题记-XIX

前言

之前把Prim和Dijkstra给混了就没发，晚上花了十多分钟搞明白刷了几道题然后发哈哈哈哈（算是复习的其实）

一些注意点

Prim和Dijkstra的区别

区别在于，Prim是算该点到已加入的点的集合的距离最小值（即cost[u][v]），而Dijkstra是算该点到源点的最小值（即cost[u][v] + d[u]）

最小生成树的表述

最小生成树是使得图能连通，加边权值之和最小的方案

由Kruskal算法可知，每次加边都选择尽量小的边加上去，因此最后得到的图也是最大边尽量小的图

Constructing Roads - HDU - 1102

题意

给定邻接矩阵，矩阵中的数值代表边的权值，再给定q条已连接的边，现求使整幅图能连通所需的边权值之和最小值

思路

MST模板题

只需把q条已连接边的权值设为0再跑最小生成树即可

Prim做法：

Kruskal做法：

Networking - POJ - 1287

题意

给定u,v,val，求MST

思路

MST模板题，只是这次用的是邻接链表

畅通工程再续 - HDU - 1875

思路

先算距离，然后把距离1000的边权值设为inf再跑MST，最终如果有点的used = false那就说明整幅图没有连通，无法完成

Truck History - POJ - 1789

题意

（简化版，英文原题十分难懂T^T）

给定一组7个字符的字符串，字符串两两之间的距离为对应位置上不同字母数之和，最开始只有一个字符串，后来的字符串由其他字符串派生出来，派生的代价为两个字符串的距离，现求得到所有字符串的代价之和最小值

思路

先算距离，然后跑MST

旅行 - SZUCPC 2017 Winter

思路

本题似乎只能用Kruskal，因为需要用并查集，另外询问次数很多因此需要离线打表

首先无疑是MST，因为价值取最大的那条路

然后用并查集动态维护每个连通块点的个数和美丽城市的个数，并动态计算出加入每一条边后答案点对的和

因为使用Kruskal，边值是升序排序的，因此最终可通过二分寻找最后一个不超过承受能力的答案并输出