排序:
#include<bits/stdc++.h>
using namespace std;
int a[1000001],n;
int b[1000001],tmp[1000001];
int GetMax(int a[],int n)
{
int max=a[0];
for(int i=1;i<n;i++){
if(a[i]>max) max = a[i];
}
return max;
}
void QuickSort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
QuickSort(q, l, j), QuickSort(q, j + 1, r);
}
int ans;
void MergeSort(int q[],int l,int r)
{
if(l==r)return;
int i=l,mid=(l+r)/2,j=mid+1,k=l;
MergeSort(q,l,mid);
MergeSort(q,mid+1,r);
while(i<=mid&&j<=r)
{
if(q[i]<=q[j]){
tmp[k++]=q[i++];
}
else{
ans=ans+j-k;
tmp[k++]=q[j++];
}
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(int i=l;i<=r;i++)
q[i]=tmp[i];
}
void MergeFindSort( int a[] , int n )
{
int low , high , mid ;
int temp ;
for ( int i=1 ; i<n ; i++ )
{
temp = a[i ];
low = 0 ;
high = i - 1 ;
while ( low <= high )
{
mid = ( low + high ) / 2 ;
if ( a[mid] > temp )
high = mid - 1 ;
else
low = mid + 1 ;
}
for ( int j = i - 1 ; j > high ; j-- )
a[j+1] = a[j] ;
a [high+1] = temp ;
}
}
void ShellSort(int arr[], int len)
{
int i, j, temp, jump=len>>1;
while (jump != 0)
{
for (i = jump; i < len; i++)
{
temp = arr[i];
j = i - jump;
while (j >= 0 && temp < arr[j])
{
arr[j + jump] = arr[j];
j=j-jump;
}
arr[j + jump] = temp;
}
jump/=2;;
}
}
void CountingSort(int a[],int n)
{
int m = GetMax(a,n);
int b[m+1]={0};
for(int j=0;j<n;j++) b[a[j]]++;
for(int i=0,k=0;i<=m||k<n;i++)
{
while(b[i]>0){
a[k++] = i;
b[i]--;
}
}
}
void RadixSort(int*a,int length)
{
int max=a[0];
for(int i=1;i<length;i++)
{
if(a[i]>max)
{
max=a[i];
}
}
int base=1;
int *b=(int*)malloc(sizeof(int)*length);
int i;
while(max/base>0)
{
int t[10]={0};
for(i=0;i<length;i++)
{
t[a[i]/base%10]++;
}
for(i=1;i<10;i++)
{
t[i]+=t[i-1];
}
for(i=length-1;i>=0;i--)
{
b[t[a[i]/base%10]-1]=a[i];
t[a[i]/base%10]--;
}
for(i=0;i<length;i++)
{
a[i]=b[i];
}
base=base*10;
}
}
void InsertSort(int* a, int n)
{
int i = 0;
for (i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void BubbleSort(int a[],int n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
void SelectSort(int arry[], int len)
{
int i;
int j;
for ( i = 0; i < len-1; i++)
{
int min = i;
for (j = i + 1; j < len; j++)
{
if (arry[j] < arry[min])
{
min = j;
}
}
int temp = arry[min];
arry[min] = arry[i];
arry[i] = temp;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<endl<<endl;
cout<<"数组a中有";
MergeSort(a,0,n-1);
cout<<ans;
stable_sort(a,a+n);
cout<<"队逆序对";
cout<<endl<<endl;
RadixSort(a,n);
CountingSort(a,n);
ShellSort(a,n);
MergeFindSort(a,n);
InsertSort(a,n);
BubbleSort(a,n);
SelectSort(a,n);
QuickSort(a,0,n-1);
sort(a,a+n);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
高精度:
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
一维前缀和:
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
二维前缀和:
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
一位差分:
给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c
二维差分:
给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
位运算:
求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n
双指针:
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类:
(1) 对于一个序列,用两个指针维护一段区间
(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
单链表:
// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除,需要保证头结点存在
void remove()
{
head = ne[head];
}
双链表:
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点,1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
快速幂
long long qmi(long long a,int b,int p)
{
long long res=1;
while(b),
{
if(b&1) res = res *a %p;
b>>=1;
a=a*a%p;
}
return res;
}
KMP:
_给定一个模式串 S,以及一个模板串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
求出模板串 P 在模式串 S 中所有出现的位置的起始下标。
输入格式
第一行输入整数 N,表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M,表示字符串 S 的长度。
第四行输入字符串 S。
输出格式
共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。_
#include<iostream>
using namespace std;
const int N=100010,M=1000010;
char q[N],s[M];
int ne[N];//保存next数组
int main()
{
int n,m;
cin>>n>>q+1>>m>>s+1;//下标均从1开始
for(int i=2,j=0;i<=n;i++)
//j表示匹配成功的长度,i表示q数组中的下标,因为q数组的下标是从1开始的,只有1个时,一定为0,所以i从2开始
{
while(j&&q[i]!=q[j+1]) j=ne[j];
//如果不行可以换到next数组
if(q[i]==q[j+1]) j++;
//成功了就加1
ne[i]=j;
//对应其下标
}
//j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度为0
for(int i=1,j=0;i<=m;i++)
{
while(j&&s[i]!=q[j+1]) j=ne[j];
//如果匹配不成功,则换到j对应的next数组中的值
if(s[i]==q[j+1]) j++;
//匹配成功了,那么j就加1,继续后面的匹配
if(j==n)//如果长度等于n了,说明已经完全匹配上去了
{
printf("%d ",i-j);
//因为题目中的下标从0开始,所以i-j不用+1;
j=ne[j];
//为了观察其后续是否还能跟S数组后面的数配对成功
}
}
return 0;
}
Trie树:
int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
并查集:
(1)朴素并查集:
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
(2)维护size的并查集:
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集:
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化,假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量
堆:
// h[N]存储堆中的值, h[1]是堆顶,x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点,及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
一般哈希:
(1) 拉链法
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
(2) 开放寻址法
int h[N];
// 如果x在哈希表中,返回x的下标;如果x不在哈希表中,返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
字符串哈希:
核心思想:将字符串看成P进制数,P的经验值是131或13331,取这两个值的冲突概率低
小技巧:取模的数用2^64,这样直接用unsigned long long存储,溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
邻接表:
// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
树与图的遍历:
时间复杂度 O(n+m)O(n+m), nn 表示点数,mm 表示边数
(1) 深度优先遍历
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
(2) 宽度优先遍历
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
拓扑排序:
时间复杂度 O(n+m)O(n+m), nn 表示点数,mm 表示边数
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了,说明存在拓扑序列;否则不存在拓扑序列。
return tt == n - 1;
}
朴素dijkstra算法:
时间复杂是 O(n2+m)O(n2+m), nn 表示点数,mm 表示边数
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中,寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
堆优化版dijkstra:
时间复杂度 O(mlogn)O(mlogn), nn 表示点数,mm 表示边数
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离,second存储节点编号
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
Bellman-Ford算法:
时间复杂度 O(nm)O(nm), nn 表示点数,mm 表示边数
注意在模板题中需要对下面的模板稍作修改,加上备份数组,详情见模板题。
int n, m; // n表示点数,m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边,a表示出点,b表示入点,w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
比如:
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 10010;
struct Edge {
int a;
int b;
int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边
int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i++) {//k次循环
memcpy(back, dist, sizeof dist);
for (int j = 0; j < m; j++) {//遍历所有边
int a = e[j].a, b = e[j].b, w = e[j].w;
dist[b] = min(dist[b], back[a] + w);
//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
else return dist[n];
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i++) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
e[i] = {a, b, w};
}
int res = bellman_ford();
if (res == -1) puts("impossible");
else cout << res;
return 0;
}
spfa 算法(队列优化的Bellman- Ford算法):
时间复杂度 平均情况下 O(m)O(m),最坏情况下 O(nm)O(nm), nn 表示点数,mm 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j,则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
spfa判断图中是否存在负环:
时间复杂度是 O(nm)O(nm), nn 表示点数,mm 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离,cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环,则返回true,否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由抽屉原理一定有两个点相同,所以存在环。
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
floyd算法:
时间复杂度是 O(n3)O(n3), nn 表示点数
初始化:
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
朴素版prim算法:
时间复杂度是 O(n2+m)O(n2+m), nn 表示点数,mm 表示边数
int n; // n表示点数
int g[N][N]; // 邻接矩阵,存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通,则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
Kruskal算法:
```cpp
时间复杂度是 O(mlogm)O(mlogm), nn 表示点数,mm 表示边数
int n, m; // n是点数,m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通,则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}