本文主要是介绍2.15总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天主要在写洛谷上的题，加上有几天没敲代码了，顺便复习了一些之前学过的东西
最小生成树（kruscal和prim）
kruscal算法要将所有的边从小到大进行排序，进行并查集的操作，将不是同一个父亲的合并，直到所有点为一个集合，合成了n-1条边（有n个点）
prim算法和dijstal算法有一些相似的地方，在所有点里任意找一个点，从这个点开始往下寻找，找到附件较小的权边为第二个点，再将两个点同时开始寻找，把相邻最小的权边确定为下一个点，以此操作，直到达到目的
P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
输入格式
第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 Xi,Yi,Zi，表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。
输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
输出
7
说明/提示
数据规模：
对于 20%20% 的数据，N≤5，M≤20。
对于 40%40% 的数据，N≤50，M≤2500。
对于 70%70% 的数据，N≤500，M≤104。
对于 100%100% 的数据：1≤N≤5000，1≤M≤2×105，1≤Zi≤104。
思路：建立结构体将样例输入后可以使用kruscal来解决，将所有的数按权边大小从小到大进行排列（要求最小就要顺序排列），依次进行并查集的操作，每合并一次cnt+1、sum加上此时的权边值,当cnt的值等于点数-1时输出结果结束程序（因为是从小到大排列，得到的自然会是最小值），否则输出orz结束程序
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int n, m,sum,counts;
int f[200005];
struct edge {int x;int y;int z;
}eg[200005];
bool cmp(edge a, edge b) {return a.z < b.z;
}
//void quicksort(int left, int right) {
// int i, j;
// i = left;
// j = right;
// struct edge t;
// while (i != j) {
// while (eg[j].z > eg[left].z && i < j)
// j--;
// while (eg[i].z < eg[left].z && i < j)
// i++;
// if (i < j) {
// t = eg[i];
// eg[i] = eg[j];
// eg[j] = t;
// }
// }
// t = eg[left];
// eg[left] = eg[i];
// eg[i] = eg[left];
// quicksort(left, i - 1);
// quicksort(i + 1, right);
// return;
//}
int find(int x) {if (f[x] == x)return x;f[x] = find(f[x]);return f[x];
}
int merge(int x, int y) {int f1 = find(x);int f2 = find(y);if (f1 != f2) {f[f1] = f2;return 1;}return 0;
}
int main() {cin >> n >> m;sum = 0, counts = 0;for (int i = 1; i <= m; i++) {cin >> eg[i].x >> eg[i].y >> eg[i].z;}for (int i = 1; i <= m; i++)f[i] = i;/*quicksort(1, m);*/sort(eg + 1, eg + 1 + m, cmp);for (int i = 1; i <= m; i++) {if (merge(eg[i].x, eg[i].y)) {counts++;sum+=eg[i].z;}if (counts == n - 1) {cout << sum;return 0;}}cout << "orz" << endl;return 0;
}P1194 买礼物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
又到了一年一度的明明生日了，明明想要买 B 样东西，巧的是，这 B 样东西价格都是 A 元。
但是，商店老板说最近有促销活动，也就是：
如果你买了第 I 样东西，再买第 J 样，那么就可以只花 KI,J 元，更巧的是，KI,J 竟然等于 KJ,I。
现在明明想知道，他最少要花多少钱。
输入格式
第一行两个整数，A,B。
接下来 B 行，每行B 个数，第 I 行第 J 个为 KI,J。
我们保证 KI,J=KJ,I 并且 KI,I=0。
特别的，如果 KI,J=0，那么表示这两样东西之间不会导致优惠。
注意 KI,J 可能大于 A。
输出格式
一个整数，为最小要花的钱数。
输入输出样例
输入
1 1 0
输出
1
输入
3 3 0 2 4 2 0 2 4 2 0
输出
7
说明/提示
样例解释 22。
先买第 22 样东西，花费 33 元，接下来因为优惠，买 1,31,3 样都只要 22 元，共 77 元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 44 元买剩下那件，而选择用 22 元。）
数据规模
对于 30%30% 的数据，1≤B≤10。
对于 100%100% 的数据，1≤B≤500,0≤A,KI,J≤1000。
思路：利用买完I后买J这个规则进行构图，把Kij的价格看成权边，每一个Kij有着自己的邻点，同样使用kruscal算法先排序，然后进行并查集操作，当原始价格A小于Kij的价格时加上A，否则加上Kij
代码：
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{int x;int y;int w;
}edge[1000005];
int fa[1000005];
bool cmp(node x, node y)
{return x.w < y.w;
}
int find(int x)
{if (x == fa[x])return x;fa[x] = find(fa[x]);return fa[x];
}
void combine(int x, int y)
{x = find(x);y = find(y);fa[x] = y;
}
int main()
{int a, b;cin >> a >> b;int jj = 0;for (int i = 1; i <= b; i++)fa[i] = i;for (int i = 1; i <= b; i++)for (int j = 1; j <= b; j++){cin >> edge[++jj].w;edge[jj].x = i;edge[jj].y = j;if (edge[jj].w == 0)edge[jj].w = a;}sort(edge + 1, edge + 1 + jj, cmp);int sum = a;for (int i = 1; i <= jj; i++){if (find(edge[i].x) != find(edge[i].y)) {combine(edge[i].x, edge[i].y);if (edge[i].w < a)sum += edge[i].w;else sum += a;}}cout << sum << endl;return 0;
}P1359 租用游艇 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
长江游艇俱乐部在长江上设置了 n 个游艇出租站1,2,⋯,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j)（1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 11 到游艇出租站 n 所需的最少租金。
输入格式
第一行中有一个正整数 n，表示有 n 个游艇出租站。接下来的 n−1 行是一个半矩阵 r(i,j)（1≤i<j≤n）。
输出格式
输出计算出的从游艇出租站 11 到游艇出租站 n 所需的最少租金。
输入输出样例
输入
3 5 15 7
输出
12
说明/提示
n≤200，保证计算过程中任何时刻数值都不超过 106。
思路：把数组补全之后用floyed，用一个二维数组来得到每两个点之间的最短距离，最后直接输出a[起始点][目标点]
代码：
#include<iostream>
using namespace std;
int main() {int n;int a[205][205];cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {a[i][j] = 999999;}}for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {cin >> a[i][j];}}for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (a[i][j] > a[i][k] + a[k][j])a[i][j] = a[i][k] + a[k][j];}}}cout << a[1][n] << endl;return 0;
}这篇关于2.15总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
