目录：
1.洛谷P3366 【模板】最小生成树
2.洛谷P1991 无线通讯网
3.洛谷P2121 拆地毯
4.洛谷P2872[USACO07DEC]Building Roads S
5.洛谷P3371 【模板】单源最短路径（弱化版）
6.洛谷P1629 邮递员送信
7. 洛谷P1359 租用游艇
8.洛谷P4779 【模板】单源最短路径（标准版）
1.洛谷P3366 【模板】最小生成树
给出一个无向图，求出最小生成树，
该图连通，则输出一个整数表示最小生成树的各边的长度之和。
如果该图不连通则输出 orz如果该图不连通，则输出 orz
输入：
第一行包含两个整数N,M表示N个结点，M个无向边
思路：Kruskal 算法求最小生成树
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 10;
int n, m,sum;
int fa[maxn];
struct node {
int x, y, z;
}edge[maxn];
bool cmp(node a, node b) {
return a.z < b.z;
}
int my_sort(int l, int r) //快排
{
if (l >= r)
return 0;
int i = l, j = r;
node t, t1 = edge[l];
while (i < j)
{
while (i < j && edge[j].z >= t1.z)
j--;
while (i < j && edge[i].z <= t1.z)
i++;
if (i < j) {
t = edge[i];
edge[i] = edge[j];
edge[j] = t;
}
}
edge[l] = edge[i];
edge[i] = t1;
my_sort(l, i - 1);
my_sort(i + 1, r);
}
int find(int x) { //找父结点
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edge[i].x >> edge[i].y >> edge[i].z;
}
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
/*sort(edge + 1, edge + 1 + m, cmp);*/
my_sort(1,m);
for (int i = 1; i <= m; i++) { //每次添加最短的一条边
int x = find(edge[i].x);
int y = find(edge[i].y);
if (x == y)continue;
fa[min(x, y)] = max(x, y);
sum += edge[i].z;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (fa[i] == i)ans++; //联通情况为所有结点父结点为同一个
}
if (ans > 1)cout << "orz" << '\n';
else cout << sum << '\n';
return 0;
}
2.洛谷P1991 无线通讯网
输入
输入数据第 1 行，2 个整数 S,P;S表示可安装的卫星电话的哨所数,P表示边防哨所的数量
接下来P行表示坐标，每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。
无线电收发器通话的哨所之间的距离不能超过 D,
任意两个配备了一条卫星电话线路的哨所（两边都ᤕ有卫星电话）均可以通话，无论他们相距多远
输出
最小D,精确到小数点后两位。
思路：
Kruskal 算法求一个平面直角坐标系中的最小生成树中满足退出条件为p – s的最小边
Kruskal算法是通过并查集，按照边的权重顺序（从小到大）将边加入生成树中，
但是若加入该边会与生成树形成环则不加入该边,选其次。直到树中含有n – 1条边为止。
这道题退出条件变成了p – s
s一定留给最远的
#include<iostream>
#include<math.h> //sqrt头文件
using namespace std;
const int maxn = 2e5 + 10;
int s, p;
int fa[maxn];
double sum=0;
struct node { //记录每座城市相连序号与距离
int x, y;
double s;
}edge[maxn];
struct recc { //记录坐标
double xx, yy;
}b[maxn];
int find(int x) { //查询父结点
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int my_sort(int l, int r) //快排
{
if (l >= r)
return 0;
int i = l, j = r;
node t, t1 = edge[l];
while (i < j)
{
while (i < j && edge[j].s >= t1.s)
j--;
while (i < j && edge[i].s <= t1.s)
i++;
if (i < j) {
t = edge[i];
edge[i] = edge[j];
edge[j] = t;
}
}
edge[l] = edge[i];
edge[i] = t1;
my_sort(l, i - 1);
my_sort(i + 1, r);
}
int main()
{
ios::sync_with_stdio(false);
cin >> s >> p;
int flag = 0;
for (int i = 1; i <= p; i++) {
fa[i] = i;
cin >> b[i].xx >> b[i].yy;
for (int j = 1; j < i; j++) {
edge[++flag].x = i;
edge[flag].y = j;
edge[flag].s= sqrt((b[i].xx - b[j].xx) * (b[i].xx - b[j].xx) + (b[i].yy - b[j].yy) * (b[i].yy - b[j].yy));//勾股定理
}
}
my_sort(1, flag);
int flag1 = 0;
for (int i = 1; i <= flag; i++) { 每次添加最短的一条边
int x = find(edge[i].x);
int y = find(edge[i].y);
if (x != y) {
fa[min(x, y)] = max(x, y);
flag1++;
if (flag1 >= p - s) {
printf("%.2f", edge[i].s);
return 0;
}
}
}
return 0;
}
3.洛谷P2121 拆地毯
会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。
每条地毯可由三个整数 u、v、w 表示，
其中 u 和 v 为地毯连接的两个关键区域编号，w 为这条地毯的美丽度。
组织者被要求只能保留 K 条地毯，
组织者要求新图中不能有环,算出这 K 条地毯的美丽度之和最大为多少。
输入格式
第一行包含三个正整数 n、m、K。
接下来 m 行中每行包含三个正整数 u、v、w。
输出格式
只包含一个正整数，表示这 K 条地毯的美丽度之和的最大值。
思路：
Kruskal算法是通过并查集，按照边的权重顺序（从小到大）将边加入生成树中，
但是若加入该边会与生成树形成环则不加入该边,选其次。直到树中含有n – 1条边为止。
这道题自需按从大到小排序，求最大生成树,退出条件为k
#include<iostream>
using namespace std;
const int maxn = 2e5 + 10;
int n, w, k;
int fa[maxn];
struct node {
int x, y, z;
}edge[maxn];
int find(int x) { //查询父结点
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int my_sort(int l, int r) //快排
{
if (l >= r)
return 0;
int i = l, j = r;
node t, t1 = edge[l];
while (i < j)
{
while (i < j && edge[j].z <= t1.z)
j--;
while (i < j && edge[i].z >= t1.z)
i++;
if (i < j) {
t = edge[i];
edge[i] = edge[j];
edge[j] = t;
}
}
edge[l] = edge[i];
edge[i] = t1;
my_sort(l, i - 1);
my_sort(i + 1, r);
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> w >> k;
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 1; i <= w; i++) {
cin >> edge[i].x >> edge[i].y >> edge[i].z;
}
my_sort(1, w); //从大到小排序
int sum = 0, flag = 0;
for (int i = 1; i <= w; i++) { 每次添加最长的一条边
int x = find(edge[i].x);
int y = find(edge[i].y);
if (x != y) {
fa[min(x, y)] = max(x, y);
sum += edge[i].z;
flag++;
if (flag == k)
break;
}
}
cout << sum << '\n';
return 0;
}
4.洛谷P2872[USACO07DEC]Building Roads S
给定 n 个点的坐标，第 i 个点的坐标为(xi, yi)，
这 n 个点编号为 1 到 n。给定 m 条边，第 i 条边连接第 ui 个点和第 vi 个点。
现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。
求添加的边的总长度的最小值。
输入：
第一行两个整数 n, m 代表点数与边数。
接下来 n 行每行两个整数 xi, yi 代表第 i 个点的坐标。
接下来 m 行每行两个整数 ui, vi 代表第 i 条边连接第 ui 个点和第 vi 个点。
输出：
一行一个实数代表添加的边的最小长度，要求保留两位小数，为了避免误差， 请用 64 位实型变量进行计算。
思路：
Kruskal算法求最小生成树，只需将一开始就存在的边权值赋为0即可
#include<iostream>
#include<math.h>//sqrt头文件
using namespace std;
const int maxn = 2e6 + 10; //需开大点，防止RE
int n, m;
int fa[maxn];
double sum = 0.0;
struct node {//记录相连点序号和距离
int x, y;
double z;
}edge[maxn];
struct recc {//记录坐标
double xx, yy;
}b[maxn];
int find(int x) { //查询父结点
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int my_sort(int l, int r) //快排
{
if (l >= r)
return 0;
int i = l, j = r;
node t, t1 = edge[l];
while (i < j)
{
while (i < j && edge[j].z >= t1.z)
j--;
while (i < j && edge[i].z <= t1.z)
i++;
if (i < j) {
t = edge[i];
edge[i] = edge[j];
edge[j] = t;
}
}
edge[l] = edge[i];
edge[i] = t1;
my_sort(l, i - 1);
my_sort(i + 1, r);
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
int flag = 0;
for (int i = 1; i <= n; i++) {
fa[i] = i;
cin >> b[i].xx >> b[i].yy;
for (int j = 1; j < i; j++) {
edge[++flag].x = i;
edge[flag].y = j;
edge[flag].z= ((b[i].xx - b[j].xx) * (b[i].xx - b[j].xx) + (b[i].yy - b[j].yy) * (b[i].yy - b[j].yy));//勾股定理
}
}
for (int i = 1; i <= m; i++) { //一开始存在的边赋为0
int x, y; //不需要更改原有边，添加即可
cin >> x >> y; //因为排序后在最前添加，添加后父结点一致，原有边不会进来
edge[++flag].x = x;
edge[flag].y = y;
edge[flag].z = 0.0;
}
my_sort(1, flag);
for (int i = 1; i <= flag; i++) { //每次添加最短的一条边
int x = find(edge[i].x);
int y = find(edge[i].y);
if (x != y) {
fa[min(x, y)] = max(x, y);
sum += sqrt(edge[i].z); //在加和的时候sqrt节省时间
}
}
printf("%.2f", sum);
return 0;
}
5.洛谷P3371 【模板】单源最短路径（弱化版）
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n, m, s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u, v, w，表示一条 u -> v 的，长度为 w 的边。
输出格式
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31 – 1。
思路：
Dijkstra算法
Dijkstra是基于一种贪心的策略，用数组dis记录起点到每个结点的最短路径，
bool 数组vis表示是否来过，dis[s]=0,其余为2的31次方-1，
定义pos变量代表现在的位置,vis[pos]=true表示来过，初始值为起点
枚举所有与pos相连的点：更新dis[i]按照：dis[i]=min(dis[i],dis[pos]+w)
枚举所有未被标记的点，找到dis最小的点赋值给pos，vis[pos]==true;
所有点都访问过程序结束。此时，dis[i]代表从起点到i的最短路径
#include<iostream>
#include<cstring>//memset头文件
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
ll dis[maxn];
bool vis[maxn];
int m, n, s;
struct edge1{
int u,w;
int next;
edge1(){}
edge1(int _u, int _w, int _next) { //简化插入操作
u = _u;
w = _w;
next = _next;
}
}edge[maxn]; //链式前向星
void insert(int u, int v, int w){//头插法
edge[++cnt]= edge1(v,w,head[u]);// 每一个新节点的next始终指向头结点的next；
head[u] = cnt;//头结点的next始终指向新结点
}
void dijkstra(int s) { //dijkstra算法
dis[s] = 0;
int pos = s;
while (!vis[pos]){
ll MIN = 2147483647;
vis[pos] = true;
for (int i = head[pos]; ~i; i = edge[i].next){ //~i==i!=-1
if (!vis[edge[i].u] && dis[edge[i].u] > dis[pos] + edge[i].w){
dis[edge[i].u] = dis[pos] + edge[i].w;
}
}
for (int i = 1; i <= m; i++){
if (dis[i] < MIN && vis[i] == 0){
MIN = dis[i];
pos = i;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> m >> n >> s;
for (int i = 1; i <= n; i++) {
dis[i] = 2147483647; //2的31次方-1;
}
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; i++) { //插入边
int u, v, w;
cin >> u >> v >> w;
insert(u, v, w);
}
dijkstra(s);
for (int i = 1; i <= m; i++){ //s到1...n的最短路径
cout << dis[i] << ' ';
}
}
6.洛谷P1629 邮递员送信
有一个邮递员要送东西，邮局在节点 1。他总共要送 n – 1样东西，
其目的地分别是节点 2到节点 n。
由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m条道路。
这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。
求送完这 n – 1 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。
第二行到第(m + 1)行，每行三个整数，u, v, w，表示从 u 到 v 有一条通过时间为 w 的道路。
输出格式
输出仅一行，包含一个整数，为最少需要的时间。
思路：
因为是有向的，所以去的时候的路线和回来时候的路线不一定是一样的。
去的时候为一对多，回来多对一，所以回来时反向建图
反图可以把所有结点的编号+ m建在原图的体系中。
需要在dijkstra函数中加入判断以区分vis，当从起点和当从终点
#include<iostream>
#include<cstring>//memset头文件
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
ll dis[maxn],sum;
bool vis[maxn];
int m, n;
struct edge1 {
int u, w;
int next;
edge1() {}
edge1(int _u, int _w, int _next) { //简化插入操作
u = _u;
w = _w;
next = _next;
}
}edge[maxn]; //链式前向星
void insert(int u, int v, int w) {//头插法
edge[++cnt] = edge1(v, w, head[u]);// 每一个新节点的next始终指向头结点的next；
head[u] = cnt;//头结点的next始终指向新结点
}
void dijkstra(int s) { //dijkstra算法
for (int i = 1; i <= m<<1; i++) {
dis[i] = 2147483647; //2的31次方-1;
}
dis[s] = 0;
int pos = s;
while (!vis[pos]) {
ll MIN = 2147483647;
vis[pos] = true;
for (int i = head[pos]; ~i; i = edge[i].next) { //~i==i!=-1
if (!vis[edge[i].u] && dis[edge[i].u] > dis[pos] + edge[i].w) {
dis[edge[i].u] = dis[pos] + edge[i].w;
}
}
if (s == 1) { //需特判起点情况
for (int i = 1; i <= m; i++) {
if (dis[i] < MIN && vis[i] == 0) {
MIN = dis[i];
pos = i;
}
}
}
else {
for (int i = 1+m; i <= m<<1; i++) {
if (dis[i] < MIN && vis[i] == 0) {
MIN = dis[i];
pos = i;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> m >> n ;
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; i++) { //插入边
int u, v, w;
cin >> u >> v >> w;
insert(u, v, w);
insert(v + m, u + m, w);
}
dijkstra(1); //去的情况
for (int i = 2; i <= m; ++i) sum += dis[i];
dijkstra(1 + m); //返回情况
for (int i = 2 + m; i <= m << 1; ++i) sum += dis[i];
cout << sum << '\n';
}
7. 洛谷P1359 租用游艇
题目描述
长江游艇俱乐部在长江上设置了n个游艇出租站1,2… n。游客可在这些游艇出租站租用游艇，
并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i, j)
试设计一个算法，计算出从游艇出租站1 到游艇出租站n所需的最少租金。
输入格式
第一行中有一个正整数n，表示有n个游艇出租站。接下来的n – 1行是一个半矩阵r(i, j)
输出格式
输出计算出的从游艇出租站1到游艇出租站n所需的最少租金。
样例
3
5 15
7
输出
12
思路:
由样例可得的大概意思：1到2点为5,1到3点为15，2到3为7，求1到n最短路径
于是转换为Dijkstra求1到n最短路径
#include<iostream>
#include<cstring>//memset头文件
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
ll dis[maxn];
bool vis[maxn];
int n, s;
struct edge1{
int u,w;
int next;
edge1(){}
edge1(int _u, int _w, int _next) { //简化插入操作
u = _u;
w = _w;
next = _next;
}
}edge[maxn]; //链式前向星
void insert(int u, int v, int w){//头插法
edge[++cnt]= edge1(v,w,head[u]);// 每一个新节点的next始终指向头结点的next；
head[u] = cnt;//头结点的next始终指向新结点
}
void dijkstra(int s) { //dijkstra算法
dis[s] = 0;
int pos = s;
while (!vis[pos]){
ll MIN = 2147483647;
vis[pos] = true;
for (int i = head[pos]; ~i; i = edge[i].next){ //~i==i!=-1
if (!vis[edge[i].u] && dis[edge[i].u] > dis[pos] + edge[i].w){
dis[edge[i].u] = dis[pos] + edge[i].w;
}
}
for (int i = 1; i <= n; i++){
if (dis[i] < MIN && vis[i] == 0){
MIN = dis[i];
pos = i;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >>n;
for (int i = 1; i <= n; i++) {
dis[i] = 2147483647; //2的31次方-1;
}
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int w;
cin >> w;
insert(i, j, w);
}
}
dijkstra(1);
cout << dis[n] << '\n';
}
8.洛谷P4779 【模板】单源最短路径（标准版）
思路：
涉及新知识点:堆优化(优先队列)和重载<
朴素Dijkstra 的方法是遍历所有的点通过比较找出最近的点
在这个地方可以使用 优先队列 来进行优化
首先将 优先队列 定义成 小根堆，将源点的距离初始化为 0 加入到优先队列中，
然后从这个点开始扩展。先将队列中的队头元素 ver 保存到一个临时变量中，
并将队头元素出队，然后遍历这个点的所有出边所到达的点 j，
更新所有到达的点距离源点最近的距离。
如果源点直接到 j 点的距离比源点先到 ver 点再从 ver 点到 j 点的距离大，
那么就更新 dis[j]，使 dis[j] 到源点的距离最短，
并将该点到源点的距离以及该点的编号加入到优先队列中，
然后将其标记，表示该点已经确定最短距离。因为是小根堆，所以会根据距离进行排序，
距离最短的点总是位于队头。一直扩展下去，直到队列为空。
#include<iostream>
#include<cstring>//memset头文件
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
int dis[maxn];
bool vis[maxn];
int m, n, s;
struct node {
int dis;
int pos;
};
struct edge1 {
int u, w;
int next;
edge1() {}
edge1(int _u, int _w, int _next) { //简化插入操作
u = _u;
w = _w;
next = _next;
}
}edge[maxn]; //链式前向星
void insert(int u, int v, int w) {//头插法
edge[++cnt] = edge1(v, w, head[u]);// 每一个新节点的next始终指向头结点的next；
head[u] = cnt;//头结点的next始终指向新结点
}
int my_sort(int l, int r) //快排
{
if (l >= r)
return 0;
int i = l, j = r;
edge1 t, t1 = edge[l];
while (i < j)
{
while (i < j && edge[j].w <= t1.w)
j--;
while (i < j && edge[i].w >= t1.w)
i++;
if (i < j) {
t = edge[i];
edge[i] = edge[j];
edge[j] = t;
}
}
edge[l] = edge[i];
edge[i] = t1;
my_sort(l, i - 1);
my_sort(i + 1, r);
}
void dijkstra(int s) { //dijkstra算法堆优化
dis[s] = 0;
queue <node>q;
q.push(node{ 0,s });
int flag = 1;
while (!q.empty()) {
node tmp = q.front();
flag--;
q.pop();
int x = tmp.pos, d = tmp.dis;//因为有 重边 的缘故，所以该点可能会有冗余数据，
if (vis[x])//遇到已经被标记的，直接 continue
continue;//忽略掉冗余数据继续扩展下一个点即可。
vis[x] = 1;
for (int i = head[x]; ~i; i = edge[i].next) {
int y = edge[i].u;
if (dis[y] > dis[x] + edge[i].w){
dis[y] = dis[x] + edge[i].w;
if (!vis[y]){
q.push(node{ dis[y], y });
flag++;
}
}
}
my_sort(1, flag);
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> m >> n >> s;
for (int i = 1; i <= n; i++) {
dis[i] = 2147483647; //2的31次方-1;
}
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; i++) { //插入边
int u, v, w;
cin >> u >> v >> w;
insert(u, v, w);
}
dijkstra(s);
for (int i = 1; i <= m; i++) { //s到1...n的最短路径
cout << dis[i] << ' ';
}
}
简化：重载<
#include<iostream>
#include<cstring>//memset头文件
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn], cnt;
int dis[maxn];
bool vis[maxn];
int m, n, s;
struct node{
int dis;
int pos;
bool operator <(const node& x)const{ //重载<
return x.dis < dis;
}
};
struct edge1{
int u,w;
int next;
edge1(){}
edge1(int _u, int _w, int _next) { //简化插入操作
u = _u;
w = _w;
next = _next;
}
}edge[maxn]; //链式前向星
void insert(int u, int v, int w){//头插法
edge[++cnt]= edge1(v,w,head[u]);// 每一个新节点的next始终指向头结点的next；
head[u] = cnt;//头结点的next始终指向新结点
}
void dijkstra(int s) { //dijkstra算法堆优化
dis[s] = 0;
std::priority_queue <node>q;
q.push(node{ 0,s });
while (!q.empty()) {
node tmp = q.top();
q.pop();
int x = tmp.pos, d = tmp.dis;
if (vis[x])
continue;
vis[x] = 1;
for (int i = head[x]; ~i; i = edge[i].next)
{
int y = edge[i].u;
if (dis[y] > dis[x] + edge[i].w)
{
dis[y] = dis[x] + edge[i].w;
if (!vis[y])
{
q.push(node { dis[y], y });
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> m >> n >> s;
for (int i = 1; i <= n; i++) {
dis[i] = 2147483647; //2的31次方-1;
}
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; i++) { //插入边
int u, v, w;
cin >> u >> v >> w;
insert(u, v, w);
}
dijkstra(s);
for (int i = 1; i <= m; i++){ //s到1...n的最短路径
cout << dis[i] << ' ';
}
}