沃特艾文儿～-CSDN博客

引入按顺序排列的的三个矩阵 M1,M2,M3计算三个矩阵相乘结果，有两种乘法（M1 M2) M3M1(M2 M3)但两种乘法计算次数不同三个矩阵维度如下4 * 5 5 * 6 6 * 7第一种计算次数4 * 5 * 6 + 4 * 6 * 7第二种计算次数5 * 6 * 7 + 4 * 5 * 7计算次数会有不同随着矩阵数量变大，计算的方式也会变得更多样，对于n个矩阵不同计算方式总数我们称之为卡特兰数。在此不多赘述。寻找最优计算方式

2022-03-23 21:20:17 764

原创选择排序模板

选择排序//// Created by 29273 on 2022-03-16.//#include "bits/stdc++.h"using namespace std;int n;int a[100];void selectSort() { for (int i = 1; i < n; ++i) { int k = i; for (int j = i + 1; j <= n; ++j) { if (a[k]

2022-03-16 16:12:23 219

原创冒泡排序基本模板

冒泡排序//// Created by 29273 on 2022-03-16.//#include "bits/stdc++.h"using namespace std;int a[100];int n;void bubbleSort() { int flag; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (a[i] > a[j

2022-03-16 15:54:26 707

原创二分查找模板

二分查找模板//// Created by 29273 on 2022-03-16.//#include "bits/stdc++.h"using namespace std;int n,x;int a[100];int binarySearch(int x) { int low = 1; int high = n; while (low <= high) { int mid = (low + high) / 2; if (

2022-03-16 15:29:59 369

原创拓扑排序简单模板

仅作记录，拓扑模板//// Created by 29273 on 2022-03-16.//#include "bits/stdc++.h"using namespace std;const int maxN = 1e4 + 10;vector<int> V[maxN];vector<int> ans;int in[maxN];int n, x, y, m;void topSort() { queue<int> Q; for (

2022-03-16 15:02:45 203

原创最短路prim算法模板

最短路prim算法模板，仅作记录//// Created by 29273 on 2022-02-23.// Prim 最短路径算法模板#include<iostream>#include "bits/stdc++.h"using namespace std;const int maxN = 1e2 + 10;#define inf 0x3f3f3f3fint n, ans, k, m, a, b, c;int dist[maxN],dist1[maxN];int vis

2022-03-16 11:09:37 206

原创 P1576 最小花费

dijkstra 模板需要对其进行改造100 = value * 汇率 1 * 汇率2 * 。。。那么汇率乘积越大越好最短路便可改造为为最长路；dis 初始化为 0 d 数组初始化为 0（最短路均初始化为inf)松弛条件判定改变if (!vis[j] && dis[j] < dis[uu] * d[uu][j]) {dis[j] = dis[uu] * d[uu][j];}、寻找dis最长的点int uu = -1;double max_dist =

2022-03-12 21:53:32 299

原创 spfa 或者 dijkstra 解决洛谷 P3905 道路重建

对于已经连接的路距离设为零，断开的道路保持原先的距离跑一遍dijkstra 或者spfa

2022-03-10 20:41:00 311 1

原创 P1451 求细胞数量 dfs

简单dfs对于每一个不为‘0’且未被访问的地方开始dfs搜索，将其连通不为‘0’的地方vis数组置为0（之后无需访问访问），ans++。//// Created by 29273 on 2022-03-09.//#include "bits/stdc++.h"using namespace std;char a[101][101];int vis[101][101];int n, m, ans;int dir[4][2] = {{1, 0}, {-1

2022-03-10 15:58:57 128

原创 P2307 迷宫并查集求解

记录一下求解代码思路并查集作为工具，每次输入新的一组数据时将所有辅助空间重置menton数组，minX，maxX来记录输入数据的最大值，最小值以及输入过的数据，因为数据输入并不是从一开始也不是n-m连续的对于每一组数据输入的每一对数据，先检验是否二者father是否相同，相同说明已经连通，再联通便会有两条路不符合题意，不同便进行连接。输入完每组数据后，再次进行运行find函数，进行路径压缩。检查每个节点的father是否一致，不一致说明不符合题意。//// Created by 29

2022-03-10 15:52:10 124

原创 floyd算法模板

原理不做赘述，仅当记录#include<bits/stdc++.h>using namespace std;const int maxn = 1010;int g[maxn][maxn];const int inf = 0x3f3f3f3f;void init(){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j) g[i][j] = 0; else g[i][j] == inf; }

2022-03-10 15:38:28 184

原创 dfs bfs求解树的直径

树的直径树上最远的两个节点之间的距离dfs两次dfs搜索第一次任一点开始进行搜索，找到距离最远点第二次从第一次最远点开始搜索再次搜索记录最远距离//// Created by 29273 on 2022-03-07.// dfs 求树的直径#include "bits/stdc++.h"using namespace std;const int maxN = 1e3 + 10;int vis[maxN];struct node { int b;

2022-03-10 15:36:12 237