模板来源
语法踩坑 强制类型转换之使用long类型的数据进行计算。括号中是重点。
1 long long temp = (long )num[i]+num[j]+num[l]+num[r];
快速排序 快速排序本身是不稳定的,但是可以采用\{data,index\}这样元组的形式,保证data相同的情况下,按照index先后顺序进行排序,就可以使得快速排序稳定。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 void quick_sort (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]); } quick_sort(q, l, j), quick_sort(q, j + 1 , r); }
快排模板 快排练习题
注意: i==j的时候,意味着这个区间的x就位于区间中央。 i,j位置的意义是j左边(包括j)的元素都小于等于x,i右边(包括i)的元素都大于等于x。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <iostream> using namespace std ;int database[5000010 ];int count = -1 ;int aim = 0 ;int n;void quick_sort (int l,int r) { if (l>=r) return ; int i = l-1 ,j = r+1 ,x = database[i+j>>1 ]; while (i<j){ do {i++;}while (database[i]<x); do j--;while (database[j]>x); if (i<j) swap(database[i],database[j]); } int idx; if (j == aim&& (l+1 ==r||i == j)){ count = database[aim]; return ; } else if (i == aim&& (l+1 ==r||i == j)){ count = database[aim]; return ; } else if (i == j && aim>j){ quick_sort(i+1 ,r); } else if (aim>j){ quick_sort(i,r); } else { quick_sort(l,j); } } int main () { scanf ("%d %d" ,&n,&aim); for (int i = 0 ;i<n;i++){ scanf ("%d" ,&database[i]); } quick_sort(0 ,n-1 ); if (count == -1 ){ printf ("%d" ,database[aim]); }else { printf ("%d" ,count); } return 0 ; }
归并排序 主要思想是分治。 递归的中界点是直接取区间中值。 快速排序的难点在于划分(把一个区间划分成两段),归并排序的难点在于合并,本质上是一个双指针算法。 为了维持归并排序的稳定,如果两个区间有相同的值,一般我们首选第一个区间。 归并排序的时间复杂度为O(nlogn)。每次合并的复杂度为O(n),共有logn层。 ‘闭区间’写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 const int N = 1000010 ;int temp[N];void merge_sort (int q[], int l, int r) { if (l >= r) return ; int mid = l + r >> 1 ; merge_sort(q, l, mid); merge_sort(q, mid + 1 , r); int k = 0 , i = l, j = mid + 1 ; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0 ; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
练习题目 教训:一定要开lld。 可以理解成状态转移,转移条件的关键在于cnt = cnt+mid-i+1这个式子。
整数二分 整数二分有两个模板,在不同情况下使用,防止稍不留神写出死循环。 算法思路:假设目标值在闭区间[l,r]中,每次将区间长度缩小一半,当l=r时,我们就找到了目标值。 有单调性的区间,一定可以二分,但是可以二分的题目,不一定非得有单调性。 整数二分的实质:我们定义了一个性质,这个性质在左半边区间是不满足的,在右半边区间是满足的,因为是整数上的二分,所以左右两个区间不存在交点。那么二分算法就可以寻找这两个区间的边界,既可以寻找左边区间的边界,也可以寻找右边区间的边界。 模板1可以二分确定红色区间的边界,模板2可以二分确定绿色区间的边界。 上图对应模板二,图片中有一处错误,mid = (l+r+1)/2。例如当l = r-1时,如果mid没有+1,mid = (l+r)/2 = l。如果check返回条件是true,则下一个区间依然传入的是[l,r],就会陷入死循环。 两个模板的选择方法:看每次更新时,check条件为真的区间,是l = mid还是r = mid
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 bool check (int x) {} int bsearch_1 (int l, int r) { while (l < r) { int mid = l + r >> 1 ; if (check(mid)) r = mid; else l = mid + 1 ; } return l; } int bsearch_2 (int l, int r) { while (l < r) { int mid = l + r + 1 >> 1 ; if (check(mid)) l = mid; else r = mid - 1 ; } return l; }
练习题目1 二分的本质是每次都要选择答案所在的区间进行下一步的处理。二分的算法一定是有解的,就是模板可以给出一个答案的,如果这个答案不符合题目要求,这个才是无解的,这是由题目给的区间中不存在相应答案导致的。练习题目
新思路:结合map来去重。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 class Solution {public : map <int ,map <int ,int >> ma; vector <int >datain; int mid_search (int l, int r, int aim) { if (datain[l] == aim) { return l; } else if (datain[r] == aim) { return r; } int mid = (l + r) / 2 ; while (r - l > 1 ) { mid = (l + r) / 2 ; if (datain[mid] >= aim) { r = mid; } else { l = mid + 1 ; } } if (datain[r] == aim) { return r; } else if (datain[l] == aim) { return l; } else { return -1 ; } } vector <vector <int >> threeSum (vector <int >& nums) { vector <vector <int >>result; sort(nums.begin (), nums.end ()); datain = nums; int len = nums.size (); for (int i = 0 ; i < len; i++) { for (int j = i + 1 ; j < len; j++) { int res = 0 - (nums[i] + nums[j]); if (j + 1 >= len) continue ; int k = mid_search(j + 1 , len - 1 , res); if (k == -1 ) continue ; int cnt = nums[i] * 100 + nums[j] * 10 + nums[k]; if (ma[nums[i]][nums[j]] != 0 ) continue ; ma[nums[i]][nums[j]] = nums[k]; if (nums[i] == 0 && nums[j] == 0 ) { ma[nums[i]][nums[j]] = 1 ; } result.push_back({ nums[i],nums[j],nums[k] }); } } return result; } };
练习题目2 练习题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int search (vector <int >& nums, int target) { int nums_len = nums.size (); int l = 0 ; int r = nums_len; int mid = 0 ; while (r-l>1 ){ mid = (l+r)/2 ; if (target<nums[mid]){ r = mid; }else { l = mid; } } if (nums[l]==target){ return l; }else { return -1 ; } }
练习题目3 其实二分算法在写的时候最需要注意的就是区间的定义方式,采用左闭右开[left,right)的定义方式,在定义初始的l和r值时就要注意这一点,在设置二分终点时也要注意这一点,在每次对区间端点赋值的时候也要注意到这一点,始终统一写法才能保证不会写出死循环。练习题目
练习题目4 练习题目 本质上是二分的第二种写法,寻找到满足i*i≤x的最大的i,也就是右端点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int mySqrt (int x) { long l = 0 ; long r = x; long mid = 0 ; while (l<r){ mid = (l+r+1 )/2 ; if (x>=mid*mid){ l = mid; }else { r = mid-1 ; } } return l; } };
浮点数二分 浮点数二分的实现中l和r赋的新值都是mid相同。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 bool check (double x) {} double bsearch_3 (double l, double r) { const double eps = 1e-6 ; while (r - l > eps) { double mid = (l + r) / 2 ; if (check(mid)) r = mid; else l = mid; } return l; }
练习题目 注意的地方:如果区间内有两个零点,那么零点定理是无效的,所以要好好利用两个根之间差距大于等于1来建立一个循环,里面是浮点数二分。 浮点数二分的对象是每个长度为1的区间。
高精度加法 大整数存储是把一个大整数存储到数组里面去。具体方式见下,这是为了在做加法的时候,可以方便地在数组的最高位补上一位数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 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; }
高精度减法 练习题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 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; } bool cmp (vector <int >&A,vector <int >&B) { if (A.size ()>B.size ()){ return A.size ()>B.size (); } for (int i = A.size ()-1 ;i>=0 ;i--){ if (A[i]!=B[i]){ return A[i]>B[i]; } } } int main () { if (cmp(A,B)){ printf ('-' ); } }
高精度乘法 A以string类型读入,B以int类型读入。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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; }
高精度除法 练习题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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; }
一维前缀和 1、注意定义S[0] = 0,方便处理边界,如1~10的元素和,为S[10]-S[0]。这样不需要对从1开始的前缀和进行特判,形式统一。 2、注意[l,r]区间内数的和的求法。 3、注意元素下标从1开始,这样才可以定义出来S[0]。 4、cin读入加速:ios::sync_with_stdio(false);其作用是使cin与标准输入输出不需要同步了。副作用是代码中不能使用scanf了。
1 2 S[i] = a[1 ] + a[2 ] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1 ]
练习题目
二维前缀和 s[i][j]的计算方法: 前缀和代码如下: 边界问题:
1 2 3 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 ]
练习题目 注意我们处理过程中,全部是从1开始的,从0开始的话可能会溢出。注意如果采用vector存储原始数据的话,和前缀和矩阵之间下标的关系。
一维差分 我们有一个a数组,我们需要构造b数组,使得a数组是b数组的前缀和。 差分的用处在于,当[l,r]区间内的所有数据全部加上一个常数C时,我们只需要$b_l+C$,那么$a_l$会自动加上C,同样$a_{l+1}$也会加上C。如果不希望$a_{r+1}$加上C,我们使$b_{r+1}-C$,这样就只有区间内的数加C了。 在初始状态,我们假定a数组中的所有元素都是0,进而我们可以推出b数组中的所有元素也都是0,然后进行len(a)次插入操作。第一次是在(1,1)区间插入$a_1$,第二次是在(2,2)区间内插入$a_2$。
1 2 3 4 5 6 7 8 9 10 11 给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1 ] -= c void insert(int l,int r,int c){ b[l]+=c; b[r+1 ]-=c; } for (int i = 1 ;i<=n;i++) insert(i,i,a[i]);for (int i = 1 ;i<=n;i++) b[i] += b[i-1 ];
二维差分 我们有一个矩阵a,我们需要构造一个矩阵b,使得矩阵a是矩阵b的前缀和矩阵。 在初始状态,我们假定a矩阵中的所有元素都是0,进而我们可以推出来b矩阵中的所有元素也都是0,然后我们再依次将a矩阵中的值插入到b矩阵中。 给b[x][y]位置的元素加上c,效果是a矩阵中[x][y]右下角的元素全部加上c。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 给以(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 void insert(int x1,int y1,int x2,int y2,int c){ b[x1][y1]+=c; b[x2+1 ][y1]-=c; b[x1][y2+1 ]-=c; b[x2+1 ][y2+1 ]+=c; } for (int i = 1 ;i<=n;i++){ for (int j = 1 ;j<=m;j++){ insert(i,j,i,j,a[i][j]); } } for (int i = 1 ;i<=n;i++){ for (int j = 1 ;j<=m;j++){ b[i][j] = b[i][j-1 ]+b[i-1 ][j]+b[i][j]-b[i-1 ][j-1 ]; } }
还原原矩阵的依据: +C的快速记录法:
位运算 位运算作为判断条件记得加括号 与&,或|,如
求n的第k位数字,右移一位表示不动。
1 2 求n的第k位数字: n >> k & 1 返回n的最后一位1 :lowbit(n) = n & -n
lowbit是树状数组的基本操作。在C++中是补码存储,如果n是正数,求-n的补码的规则是各位取反,末位加一,即-n = ~n+1,具体原理在第二个图中。 我们可以用lowbit(x)来求x中1的个数。基本思想是当x不是0的时候,每次减去x的最后一位1。
1 2 3 4 while (x){ x = x-lowbit(x); res++; }
人类做题的过程实际上就是DFS的过程。
双指针算法 双指针算法的第一种形式——归并排序,一个指针指向序列A,一个指针指向序列B;第二种形式——快速排序,两个指针指向同一个序列,一个在开始的位置,一个在结束的位置。
1 2 3 4 5 6 7 8 9 10 for (int i = 0 , j = 0 ; i < n; i ++ ){ while (j < i && check(i, j)) j ++ ; } 常见问题分类: (1 ) 对于一个序列,用两个指针维护一段区间 (2 ) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
双指针算法最大的优势在于其时间复杂度一直都是O(n),而上图中的普通算法复杂度为O(n^2)。一般来说我们可以先想一个朴素做法,然后再想一下如何去优化他。 例如,输入一串字符串,每个单词以空格隔开,可以用双指针实现:i指向单词的第一个位置,j指向单词后的空格。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream> #include <string> using namespace std ;int main () { char str[1000 ]; gets(str); int n = strlen (str); for (int i = 0 ;str[i];i++){ int j = i; while (j<n&&str[j]!=' ' ) j++; for (int k = i;k<j;k++){ cout <<str[k]; } cout <<endl ; i = j; } }
双指针算法寻找序列中的连续最长不重复子序列。 左边max应该是i-j+1。 图中的check方法是确定(j,i)之间是否有重复元素。具体方法是开一个大小等于数据范围的数组。具体方法图下图: 当我们发现(j,i)区间内有重复的时候,那么重复的一定是刚刚加入的a[j],因此我们check处的条件可以替换为$a_j!=a_i$,将j指针一直移动到和$a_i$重复的元素的位置。 该题目的关键代码为:
1 2 3 4 5 6 7 8 9 for (int i = 0 ,j = 0 ;i<n;i++){ s[a[i]]++; while (s[a[i]]>1 ){ s[a[j]]--; j++; } res = max (res,i-j+1 ); }
离散化 整数的离散化,保序的离散化。输入的数据范围非常大,但是个数比较少。当我们在处理过程中要以输入的数据作为下标时,我们可以采用离散化的方法把他们映射到从0开始的自然数。 离散化第一步中去重的工作,是由unique函数和erase方法搭配完成的。 离散化的本质是坐标映射。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 vector <int > alls; sort(alls.begin (), alls.end ()); alls.erase(unique(alls.begin (), alls.end ()), alls.end ()); int find (int x) { int l = 0 , r = alls.size () - 1 ; while (l < r) { int mid = l + r >> 1 ; if (alls[mid] >= x) r = mid; else l = mid + 1 ; } return r + 1 ; }
例子:区间和的查询,在数据范围小的情况下可以用前缀和来解决,在数据范围大的情况下,就需要用离散化进行一个坐标的映射,再使用前缀和处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #include <iostream> #include <vector> #include <algorithm> using namespace std ;using PII = pair<int ,int >;const int N = 300010 ;int n,m;int a[N],s[N];vector <int > alls;vector <PII> add,query;int find (int x) { int l = 0 ,r = alls.size ()-1 ; while (l<r){ mid = (l+r)>>1 ; if (alls[mid]>=x){ r = mid; }else { l = mid+1 ; } } return r+1 ; } int main () { cin >>n>>m; for (int i = 0 ;i<n;i++){ int x,c; cin >>x>>c; add.push_back({x,c}); alls.push_back(x) } for (int i = 0 ;i<m;i++) { int l,r; cin >>l>>r; query.push_back({l,r}); alls.push_back(l); alls.push_back(r); } sort(alls.begin (),alls.end ()); alls.erase(unique(alls.begin (),alls.end ()),alls.end ()); for (auto item:add){ int x = find (item.first); a[x]+=item.second; } for (int i = 1 ;i<=alls.size ();i++){ s[i] = s[i-1 ]+a[i]; } for (auto item:query){ int l = find (item.first),r = find (item.second); cout <<s[r]-s[l-1 ]<<endl ; } }
unique函数的原理,双指针原理:如果i是第一个元素(i == 0)或者a[i]!=a[i-1],那么他就不是重复元素。就令a[j++] = a[i] 双指针算法,一个指针i用来遍历数组,另一个指针j用来记录当前存储的元素位置。 最终从0到j-1就都是不重复的元素,我们返回a.begin()+j就可以。练习题目
区间合并 区间合并的功能在于快速地将两个有交集的区间进行合并。 规定:两个区间即使只有端点相交也会进行合并。 下一个区间的三种情况: 1)包含->当前维护区间不变 2)有交集但是有一部分出去了->当前维护区间右端点变大 3)没有交集->当前维护区间左右端点都变化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 void merge (vector <PII> &segs) { vector <PII> res; sort(segs.begin (), segs.end ()); int st = -2e9 , ed = -2e9 ; for (auto seg : segs) if (ed < seg.first) { if (st != -2e9 ||segs[0 ].first == -2e9 ) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else ed = max (ed, seg.second); if (st != -2e9 ) res.push_back({st, ed}); segs = res; } int main () { cin >>n; for (int i = 0 ;i<n;i++){ int l,r; cin >>l>>r; segs.push_back({l,r}); } merge(segs); }
练习题目
单链表 数组模拟实现(静态链表)。用的最多的是邻接表。邻接表的本质是n个链表。它的基本应用是存储图和树。 空节点的下标用-1来表示。 在实现中我们使用头插法来插入新节点。头节点由原来的A指向新插入的节点,新插入的节点的next指针指向A。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 int head, e[N], ne[N], idx;void init () { head = -1 ; idx = 0 ; } void insert (int a) { e[idx] = a, ne[idx] = head, head = idx ++ ; } void remove () { head = ne[head]; } void add (int k,int a) { e[idx] = a; ne[idx] = ne[k]; ne[k] = idx; } void remove (int k) { ne[k] = ne[ne[k]]; } for (int i = head;i!=-1 ;i = ne[i]){ cout <<e[i]<<" " ; }
注意在该模板中,下标为0的是第一个插入的节点。 单链表无法找到a节点的上一个节点。
双链表 双链表的作用是优化某些问题。 双链表的插入操作。 双链表的删除操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 int e[N], l[N], r[N], idx;void init () { r[0 ] = 1 , l[1 ] = 0 ; idx = 2 ; } void insert (int a, int x) { e[idx] = x; l[idx] = a, r[idx] = r[a]; l[r[a]] = idx, r[a] = idx ++ ; } void remove (int a) { l[r[a]] = l[a]; r[l[a]] = r[a]; }
模拟栈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int stk[N], tt = 0 ;stk[ ++ tt] = x; tt -- ; stk[tt]; if (tt > 0 ){ }
队列 普通队列 在队尾插入元素,在队头弹出元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int q[N], hh = 0 , tt = -1 ;q[ ++ tt] = x; hh ++ ; q[hh]; if (hh <= tt){ }
循环队列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int q[N], hh = 0 , tt = 0 ;q[tt ++ ] = x; if (tt == N) tt = 0 ;hh ++ ; if (hh == N) hh = 0 ;q[hh]; if (hh != tt){ }
单调栈 单调栈的典型应用:1)链表与邻接表 2)栈与队列 3)KMP 下图为暴力解法 找到$a_i >a_j$的位置输出$a_j$。 暴力做法的实质是有一个栈,在i指针右移的过程中,不断将i指针左边的元素入栈。然后从栈顶开始找符合要求的元素。但是这种方法我们可以发现,有些元素怎样都不会成为答案。例如在数组中,若$a_3>a_5$,那么$a_3$永远不会成为答案。因为如果$a_i>a_3$,那么$a_i>a_5$一定成立,但是$a_5$一定距离i点更近。 单调栈内的数据特点如图,不符合的点全部删掉。每次一个新的点入栈的时候,如果栈顶$top>a_{in}$,那么栈顶就可以删掉,因为它变成了永远不会成为答案的元素。当$ top< a_i $ 时,top就是我们要找的点。练习题目
1 2 3 4 5 6 7 常见模型:找出每个数左边离它最近的比它大/小的数 int tt = 0 ;for (int i = 1 ; i <= n; i ++ ){ while (tt && check(stk[tt], i)) tt -- ; stk[ ++ tt] = i; }
例题代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <iostream> using namespace std ;const int N = 100010 ;int n;int stk[N],tt;int main () { cin >>n; for (int i = 0 ;i<n;i++){ int x; cin >>x; while (tt&&stk[tt]>=x){ tt--; } if (tt) cout <<stk[tt]<<endl ; else cout <<-1 <<endl ; stk[++tt] = x; } } cin .tie(0 );ios::sync_with_stdio(false );
单调队列 保证队列里存的都是当前窗口的所有元素,在队列满了之后,每滑动一次窗口,就要先把滑出窗口的元素出队,再将滑入窗口的元素入队。练习题目 例题是练习题目的改版,是要求区间中的最小值。 单调队列的精髓也在于及时去掉不可能成为答案的元素,比如上图中的3,只要-3在队列中,3就永远不可能成为答案,而-3还是不可能比3早出队列的,因此我们可以把3删掉。-1也是同理,可以删掉。 我们可以归纳出删掉元素a的特征:a在b的前面,且a>b,那么我们删掉a。 上图就是删掉不可能成为答案的元素之后,单调队列中元素的特征。如果我们要求一个严格单调上升队列的最小值,就是该队列的第一个元素。在有单调性的队列中,也可以用二分查找。多重背包有可以用单调队列优化。 单调队列中存的不是值,是下标。 用数组模拟的队列的好处,是比stl速度更快。
1 2 3 4 5 6 7 8 常见模型:找出滑动窗口中的最大值/最小值 int hh = 0 , tt = -1 ;for (int i = 0 ; i < n; i ++ ){ while (hh <= tt && check_out(q[hh])) hh ++ ; while (hh <= tt && check(q[tt], i)) tt -- ; q[ ++ tt] = i; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <iostream> using namespace std ;const int N = 1000010 ;int n,k;int a[N],q[N];int main () { scanf ("%d %d" ,&n,&k); for (int i = 0 ;i<n;i++){ scanf ("%d" ,&a[i]); } int hh = 0 ,tt = -1 ; for (int i = 0 ;i<n;i++){ if (hh<=tt&(i-k+1 >q[hh])){ hh++; } while (hh<=tt&&a[q[tt]]>=a[i]){ tt--; } q[++tt] = i; if (i>=k-1 ){ printf ("%d " ,a[q[hh]]); } if (hh<=tt&&(i-k+1 >q[hh])){ hh++; } while (hh<=tt&&a[q[tt]]<=a[i]){ tt--; } q[++tt] = i; if (i>=k-1 ){ printf ("%d " ,a[q[hh]]); } } return 0 ; }
KMP 这里写的有问题,kmp模板参考kmp 01:57:23 KMP下标习惯从1开始 上图中是朴素的字符串匹配算法。 上图说明了’next[i] = j’的含义是p数组中从1到j的元素和p数组中从i-j+1到i的元素全部相等。 上图中显示的是P串和S串的坐标对应关系,当模式串P在j+1处和S串不相等时,我们直接调用next[j],将j赋值为next[j],则此时P串完成了后移。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 求模式串的Next数组: for (int i = 2 , j = 0 ; i <= m; i ++ ){ while (j && p[i] != p[j + 1 ]) j = ne[j]; if (p[i] == p[j + 1 ]) j ++ ; ne[i] = j; } for (int i = 1 , j = 0 ; i <= n; i ++ ){ while (j && s[i] != p[j + 1 ]) j = ne[j]; if (s[i] == p[j + 1 ]) j ++ ; if (j == m) { j = ne[j]; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <iostream> using namespace std ;const int M = 10010 ,M = 100010 ;int n,m;char p[N],s[M];int ne[N];int main () { cin >>n>>p+1 >>m>>s+1 ; next[1 ] = 0 for (int i = 2 ,j = 0 ;i<=n;i++){ while (j&&p[i]!=p[j+1 ]){ j = ne[j]; } if (p[i] == p[j+1 ]){ j++; } ne[i] = j; } for (int i = 1 ,j = 0 ;i<=m;i++){ while (j&&s[i]!=p[j+1 ]){ j = ne[j]; if (s[i]==p[j+1 ]){ j++; } if (j == n){ printf ("%d " ,i-n+1 ); j = ne[j]; } } } return 0 ; }
使用定义计算next数组时,前缀是从左到右,后缀也是从左到右看。第i个公共前缀的长度必须小于i。练习题目 05
Trie树 Trie树是用来高效地存储和查找字符串集合。使用trie的题目中字符串一般要么全是小写字母,要么全是大写字母,要么全是数字。下图是一个例子,我们用该字符串集合创建一个Trie树。 在将第一个字符串插入到Trie树后,此时的树为 在插入第二个字符串之后Trie树的状态为 依次类推,最终的Trie树为 我们会在每个字符串结尾处打一个标记。否则如果有一个单词是另一个单词的前缀,我们在树中很有可能发现不了这个单词。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 int son[N][26 ], cnt[N], idx;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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <iostream> using namespace std ;const in N = 100010 ;int son[N][26 ],cnt[N],idx;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]; }
练习题目 练习题目 00:25:40
并查集 并查集的特点:1)将两个集合合并;2)询问两个元素是否在一个集合当中。 并查集可以在近乎O(1)的时间复杂度内完成这两个操作。 并查集的结构如上图,father节点,最后一个集合有一个代表元素。 并查集的基本原理:每一个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储存储他的父节点,p[x]表示x的父节点。 问题1:如何判断树根 if(p[x] == x),这也意味着,除了根节点之外,p[x]!=x。 问题2:如何求x的集合编号 while(p[x]!=x)x = p[x]; 问题3:如何合并两个集合 p[x]是x的集合编号,p[y]是y的集合编号,p[x] = y就是合并了两个集合。 一般按秩合并优化不怎么明显,如果要优化,推荐路径压缩。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 (1 )朴素并查集: int p[N]; int find (int x) { if (p[x] != x) p[x] = find (p[x]); return p[x]; } for (int i = 1 ; i <= n; i ++ ) p[i] = i; p[find (a)] = find (b); (2 )维护size 的并查集: int p[N], size [N]; int find (int x) { if (p[x] != x) p[x] = find (p[x]); return p[x]; } for (int i = 1 ; i <= n; i ++ ) { p[i] = i; size [i] = 1 ; } size [find (b)] += size [find (a)]; p[find (a)] = find (b); (3 )维护到祖宗节点距离的并查集: int p[N], d[N]; int find (int x) { if (p[x] != x) { int u = find (p[x]); d[x] += d[p[x]]; p[x] = u; } return p[x]; } for (int i = 1 ; i <= n; i ++ ) { p[i] = i; d[i] = 0 ; } p[find (a)] = find (b); d[find (a)] = distance;
例题题目如下: 例题加强版:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include <iostream> using namespace std ;const int N = 10010 ;int n,m;int p[N];int size [N];int find (int x) { if (p[x]!=x){ p[x] =find (p[x]); } return p[x]; } int main () { cin >>n>>m; scanf ("%d %d" ,&n,&m); for (int i = 1 ;i<=n;i++){ p[i] = i; size [i] = 1 ; } while (m--){ char op[2 ]; int a,b; scanf ("%s %d %d" ,op,&a,&b); if (op[0 ] == 'M' ){ if (find (a)==find (b)){ continue ; } p[find (a)] = find (b); size [find (b)]+=size [find (a)]; }else if (op[0 ]=='Q' ){ if (find (a) == find (b)){ printf ("yes" ); }else { printf ("no" ); } }else { scanf ("%d" ,&a); printf ("%d\n" ,size [find (a)]); } } return 0 ; }
在一个连通块中,a可以到达b,b也可以到达a。 下图为更新size的思路,b为更新后的根节点。 01:09:49
堆 堆的基本操作:1)插入一个数 2)求集合当中的最小值 3)删除最小值 (前三个STL支持) 4)删除任意一个元素 5)修改任意一个元素。 堆的特点:是一个完全二叉树,除了最后一层节点不满,从左到右排列。 小根堆:每一个点都是小于等于左右儿子的。 堆的存储如下: 两个基本操作,down和up。 下标是从1开始的,因为如果从0开始的,2x结果就还是0,冲突了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 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 ; } } for (int i = n / 2 ; i; i -- ) down(i);void insert (int x) { h[++size ] = x; up(size ); } return h[1 ];h[1 ] = h[size ]; size --;down(1 ); h[k] = h[size ]; size --;down(k); up(k); h[k] = x; down(k); up(k);
06
哈希表 哈希函数的映射方法一般是简单地取模,但是要求是一个质数,而且这个质数要距离2的整次幂尽可能的远。 离散化是一种特殊的哈希方式,因为离散化的hash结果要求保序。 拉链法,创建一个大小为模的大小的数组,看成链表头节点的集合,然后用数据hash后值作为索引,寻找对应的头节点,将该数据插入到该头节点对应的链表中。有点类似于桶排序。 hash算法是一个期望算法,每条链上的元素可以认为是常数个。 要实现删除,一般是创建一个数据,为删除的元素打上一个标记。 哈希表的时间复杂度是O(1),一般是不会和sort结合使用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 (1 ) 拉链法 int h[N], e[N], ne[N], idx; memset (h,-1 ,sizeof (h)); 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]; int null = 0x3f3f3f3f ; memset (h,0x3f ,sizeof (h)); 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; } void insert (int x) { int k = find (x); h[k] = x; } void find_elem (int x) { int k = find (x); if (h[k]!=null){ cout <<"Yes" <<endl ; }else { cout <<"No" <<endl ; } }
00:47:20 字符串前缀哈希法。首先预处理好所有前缀的哈希。定义h[0] = 0。 根本思路是把字符串看成p进制的数字。例子如下: 通过模Q可以将该字符串映射到0~Q-1的范围上去。 注意:不能将字母映射到0。比如A映射成0,那么字符串AA映射成00,这就导致不同的字符串有了相同哈希值。 而且假定我们的人品足够好,不考虑冲突情况。 我们可以通过前缀的哈希计算出子串的哈希。 计算过程:
1) 把H[L-1]这一段向右平移到和H[R]对齐的位置。即$H[L-1]\times P^{R-L+1}$ 2) $hash[L-R] = H[R]-H[L-1]\times P^{R-L+1}$
由上式可得,对于一个区间长度为1的区间来说,L = R,str(i) = H(i)-H(i-1)P,因此在计算前缀和的hash时,H(i) = H(i-1)\ P+str(i)。 例题:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 核心思想:将字符串看成P进制数,P的经验值是131 或13331 ,取这两个值的冲突概率低 小技巧:取模的数用2 ^64 ,这样直接用unsigned long long 存储,溢出的结果就是取模的结果 typedef unsigned long long ULL;ULL h[N], p[N]; p[0 ] = 1 ; for (int i = 1 ; i <= n; i ++ ){ h[i] = h[i - 1 ] * P + str[i]; p[i] = p[i - 1 ] * P; } ULL get (int l, int r) { return h[r] - h[l - 1 ] * p[r - l + 1 ]; }
例题代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <iostream> using namespace std ;using ULL = unsigned long long ;const int N = 100010 ,P = 131 ;int n,m;char str[N];ULL h[N],p[N]; UUL get (int l,int r) { return h[r]-h[l-1 ]*p[r-l+1 ]; } int main () { scanf ("%d%d%s" ,&n,&m,str+1 ); p[0 ] = 1 ; for (int i = 1 ;i<=n;i++){ p[i] = p[i-1 ]*p; h[i] = h[i-1 ]*p+str[i]; } while (m--){ int l1,r1,l2,r2; scanf ("%d%d%d%d" ,&l1,&r1,&l2,&r2); if (get (l1,r1) == get (l2,r2)){ cout <<"Yes" <<endl ; }else { cout <<"No" <<endl ; } } }
KMP可以用来求字符串的循环节,但是hash不可以。其他的功能hash都可以代替KMP。 01:12:17
C++ STL 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 vector , 变长数组,倍增的思想:当系统为某一个程序分配空间的时候,所需时间,与空间大小无关,与请求次数有关。例如,最开始先给vector 分配一个32 的空间,当不够用的时候,下一次申请的空间大小为64 ,并将32 内的数据copy到64 中去。 size () 返回元素个数,所有容器都有 empty() 返回是否为空,所有容器都有 clear () 清空,并不是所有容器都有,queue 就没有 front()/back() push_back()/pop_back() begin ()/end () []支持随机寻址 使用迭代器来遍历 for (vector <int >::iterator i = a.begin ();i!=a.end ();i++) cout <<*i<<endl for (auto x:a) cout <<x<<endl ; 支持比较运算,按字典序 vector <int >a(4 ,3 ),b(3 ,4 ); if (a<b){ cout <<"a<b" <<endl ; } pair<int , int > 可以存储一个二元组,相当于C++定义的一个结构体,自带一个比较函数 first, 第一个元素 second, 第二个元素 支持比较运算,以first为第一关键字,以second为第二关键字(字典序) pair<int ,string >p; p = make_pair(10 ,"kongming" ); p = (20 ,"abc" ); pair<int ,pair<int ,int >>p; string ,字符串 size ()/length() 返回字符串长度 empty() clear () substr(起始下标,(子串长度)) 返回子串,当子串长度大于字符串长度时,会返回到字符串结尾。字串长度是可选参数,默认值是字符串结尾。 cout <<a.substr(1 ,2 )<<endl ; c_str() 返回字符串所在字符数组的起始地址,在使用printf 函数输出字符串时用得到。 printf ("%s\n" ,a.c_str()); 重载了+运算符,可以支持两个字符串相加,或是一个字符串和一个字符相加。 queue , 队列,没有claer()函数 #include <queue> 如果想要清空queue ,只需要重新构造一个queue q = queue <int >(); size () empty() push() 向队尾插入一个元素 front() 返回队头元素 back() 返回队尾元素 pop() 弹出队头元素 priority_queue, 优先队列,默认是大根堆,没有clear 函数 size () empty() push() 插入一个元素 top() 返回堆顶元素 pop() 弹出堆顶元素 默认是大根堆,我们如果需要小根堆,可以每次向优先队列中插入-x。 定义成小根堆的方式:priority_queue<int , vector <int >, greater<int >> q; stack , 栈 size () empty() push() 向栈顶插入一个元素 top() 返回栈顶元素 pop() 弹出栈顶元素 deque , 双端队列,队头和队尾都可以插入删除,还可以支持随机访问,是一个加强版的vector ,速度稍慢一点 size () empty() clear () front()/back() push_back()/pop_back() push_front()/pop_front() begin ()/end () [] set , map , multiset , multimap , 基于平衡二叉树(红黑树),动态维护有序序列 如果在set 中插入重复元素,这个操作将会被忽略。 size () empty() clear () begin ()/end () 迭代器支持++, -- 返回前驱和后继,时间复杂度 O(logn) set /multiset insert() 插入一个数 logn的复杂度 find () 查找一个数 count() 返回某一个数的个数 erase() (1) 输入是一个数x,删除所有x O(k + logn) k是x的个数 (2 ) 输入一个迭代器,删除这个迭代器 lower_bound()/upper_bound() lower_bound(x) 返回大于等于x的最小的数的迭代器 这个包括x upper_bound(x) 返回大于x的最小的数的迭代器 这个不包括x map /multimap ,除了size ,empty之外,其他操作包括 ++ --操作复杂度都是logn。 insert() 插入的数是一个pair,map 可以像数组那种对一个键值对赋值,访问也可以用数组方式。 erase() 输入的参数是pair或者迭代器 find () [] 注意multimap 不支持此操作。 时间复杂度是 O(logn) lower_bound()/upper_bound() unordered_set , unordered_map , unordered_multiset , unordered_multimap , 哈希表 #include <unordered_map> 和上面类似,增删改查的时间复杂度是 O(1 ) 不支持 lower_bound()/upper_bound(), 迭代器的++,--,因为内部是无序的。 bitset , 压位 C++里面的bool 类型的大小是一个字节。如果我们需要1024 个bool 类型的变量,就需要1024 *8b it,但是如果我们使用1b it来记录一个bool 值,就只需要1024b it。 bitset <10000> s; ~, &, |, ^ >>, <<//移位 ==, != [] count() 返回有多少个1 any() 判断是否至少有一个1 none() 判断是否全为0 set () 把所有位置成1 set (k, v) 将第k位变成v reset() 把所有位变成0 flip() 等价于~ flip(k) 把第k位取反
具体使用:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> using namespace std ;vector <int >a(10 );vector <int >a(10 ,3 );vector <int >a[10 ];
07
树与图的遍历 DFS 回溯+剪枝 DFS最重要的就是要考虑好顺序。 虽然DFS看起来是一棵树,但是我们在存储的时候,只存储当前的路径。 在进行回溯操作的时候,一定要记得恢复现场。 思路一,枚举每一个皇后能放到哪一行。在放完最后一个皇后之后判断是否满足题目要求。也可以在放置皇后的过程中,不断判断有没有冲突
1 2 3 4 5 6 7 8 9 10 int dfs (int u) { st[u] = true ; for (int i = h[u]; i != -1 ; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <iostream> using namespace std ;const int N = 10 ;int n;int path[N];bool st[N];void dfs (int u) { if (u == n){ for (int i = 0 ;i<n;i++){ cout <<path[i]<<" " ; return ; } } for (int i = 1 ;i<=n;i++){ if (!st[i]){ path[u] = i; st[i] = true ; dfs(u+1 ); st[i] = false ; } } } int main () { cin >>n; dfs(0 ); return 0 ; }
n皇后问题思路二:对每个格子进行dfs,有放下和不放下两种选择,放下的时候要注意检查是否满足条件。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <iostream> const int N = 20 ;int n;char g[N][N];bool col[N],dg[N],udg[N],row[N];void dfs (int x,int y,int s) { if (y == n){ y = 0 ; x++; } if (x == n){ if (s == n){ for (int i = 0 ;i<n;i++){ cout <<g[i]; } cout <<endl ; } return ; } dfs(x,y+1 ,s); if (!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){ g[x][y] = 'Q' ; row[x] = col[y] = dg[x+y] = udg[x-y+n] = true ; dfs(x,y+1 ,s+1 ); row[x] = col[y] = dg[x+y] = udg[x-y+n] = false ; g[x][y] = '.' ; } }
00:55:07 BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 queue <int > q;st[1 ] = true ; 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 ; q.push(j); } } }
BFS例题答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include <iostream> #include <algorithm> #include <queue> #include <cstring> using namespace std ;using PII = pari<int ,int >;const int N = 110 ;int n,mint g[N][N];int d[N][N];PII prev[N][N]; queue <int > q;int BFS () { PII start = {0 ,0 }; q.push(start); memset (d,-1 ,sizeof (d)); d[0 ][0 ] = 0 ; int dx[4 ] = {-1 ,0 ,1 ,0 },dy[4 ] = {0 ,1 ,0 ,-1 }; while (!q.empty()){ auto t = q.top(); q.pop(); for (int i = 0 ;i<4 ;i++){ int x = t.first+dx[i],y = t.second+dy[i]; if (x>=0 &&x<n&&y>=0 &&y<m&&g[x][y] == 0 &&d[x][y]!=-1 ){ d[x][y] = d[t.first][t.second]+1 ; prev[x][y] = t; q.push({x,y}); } } } int x = n-1 ,y = m-1 ; while (x||y){ cout <<x<<" " <<y<<endl ; auto t = prev[x][y]; x = t.first,y = t.second; } return d[n-1 ][m-1 ]; } int main () { cin >>n>>m; for (int i = 0 ;i<n;i++){ for (int j = 0 ;j<n;j++){ cin >>g[i][j]; } } cout <<BFS()<<endl ; }
01:17:08
树与图的存储 树是特殊的图。树是无环连通图。因此我们只会探讨图。图分为有向图和无向图。无向图是一种特殊的有向图。要存储一个无向图ab,则需要建立两条边,a->b和b->a。 有向图的存储方法一般为两种: 1)邻接矩阵。g[a,b]表示a到b这条边的信息。 2)邻接表。 树的重心
1 2 3 4 5 6 7 8 9 10 11 12 int h[N], e[N], ne[N], idx;void add (int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } idx = 0 ; memset (h, -1 , sizeof h);
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <iostream> #include <cstring> #include <algorithm> const int N = 100010 ,M = N/2 ;int ans = N;int st[N];int h[N],e[M],idx;void add (int a,int b) { e[idx] = b,ne[idx] = h[a],h[a] = idx++; } int dfs (int u) { st[u] = true ; for (int i = h[u]; i != -1 ; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); } } int main () { memset (h,-1 ,sizeof h); cin >>n; for (int i = 0 ;i<n-1 ;i++){ int a,b; cin >>a>>b; add(a,b),add(b,a); } dfs(1 ); cout <<ans<<endl ; return 0 ; }
例题的答案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int dfs (int u) { st[u] = true ; int sum = 1 ; int res = 0 ; for (int i = h[u];i!=-1 ;i = ne[i]){ int j = e[i]; if (!st[j]){ int s= dfs(j); res = max (res,s); sum = s+sum; } } res = max (res,n-sum); ans = min (ans,res); return sum; }
01:47:05 BFS算法 “所有边的长度为1”就暗示着可以用bfs来求解最短路。 题目如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <iostream> #include <cstring> #include <algorithm> using namespace std ;const int N = 100010 ;int n,m;int h[N],e[N],ne[N],idx;int d[N],q[N];int main () { cin >>n>>m; memset (h,-1 ,sizeof h); for (int i = ) }
图的bfs例题。 利用bfs求距离。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <iostream> #include <cstring> #include <algorithm> using namespace std ;const int N = 100010 ;int n, m;int h[N], e[N], ne[N], idx;int d[N], q[N];void add (int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int bfs () { int hh = 0 , tt = 0 ; q[0 ] = 1 ; memset (d, -1 , sizeof d); while (hh <= tt) { int t = q[hh++]; for (int i = h[t]; i != -1 ; i = ne[i]) { int j = e[i]; if (d[j] == -1 ) { d[j] = d[t] + 1 ; q[++t] = j; } } } return d[n]; } int main () { cin >> n >> m; memset (h, -1 , sizeof h); for (int i = 0 ; i < m; i++) { int a, b; cin >> a >> b; add(a, b); } cout << bfs() << endl ; return 0 ; }
图的bfs的经典应用就是求拓扑序。 有向图的拓扑序列。 特点:从起点出发指向终点,完成事情的顺序。 有环的情况下就不存在拓扑序。可以证明,一个有向无环图一定存在拓扑序。因此,有向无环图也可以称为拓扑图。 度数: 当前入度为0的点都是可以作为起点的。因此拓扑排序的第一步就是把所有入度为0的点入队,例如此时队头元素为t。然后枚举t的所有出边,t->j。删掉t,意味着此时条件t已经被满足,从而影响了j的入度,j的入度dj需要减一。如果此时dj==0,那么就让j入队。 一个无环图,一定至少存在一个入度为0的点。 一个有向无环的拓扑序是不唯一的。 bfs思想实现拓扑排序代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <iostream> #include <algorithm> #include <cstring> using namespace std ;const int N = 100010 ;int n, m;int h[N], e[N], ne[N], idx;int q[N], d[N];void add (int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } bool topsort () { int hh = 0 , tt = -1 ; for (int i = 1 ; i <= n; i++) { if (!d[i]) { q[++t] = i; } } while (hh <= tt) { int t = q[hh++]; for (int i = h[t]; i != -1 ; i = ne[i]) { int j = e[i]; d[j]--; if (d[j] == 0 ) { q[++tt] = j; } } } return tt == n-1 } int main() { cin >> n >> m; memset (h, -1 , sizeof h); for (int i = 0 ; i < m; i++) { int a, b; cin >> a >> b; add(a, b); d[b]++; } if (topsort()) { for (int i = 0 ; i < n; i++) { cout << q[i] << " " ; } } else { cout << -1 << endl ; } return 0 ; }
拓扑排序要注意的是,条件是头节点,计算的度数是被条件限制的对象。
朴素dijkstra算法 最短路问题通常分为两类。 1)单源最短路。求一个点到所有点的最短距离。稠密图边数m是点数n方级别的。 2)多源汇最短路。源指的是起点,汇点指的是终点。 不超过k条边用BF比较好。 先初始化距离,dis1=0,其余是正无穷。然后找出不在s中距离最近的点q,将q点加入集合s中,确定q的最短距离,并用q来更新dis数组。 两层循环,复杂度是n^2的。 稠密图用邻接矩阵来存储,稀疏图用邻接表来存储。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 int g[N][N]; int dist[N]; bool st[N]; 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; 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]; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <iostream> #include <cstring> #include <algorithm> using namespace std ;const int N = 510 ;int n,m;int g[N][N];int dist[N];bool st[N];int dijkstra () { memset (dist,0x3f ,sizeof dist); dist[1 ] = 0 ; for (int i = 0 ;i<n;i++){ int t = -1 ; for (int j = 1 ;i<=n;j++){ if ((!st[j])&&(t == -1 ||dist[t]>dist[j])){ t = j; } } if (t == n) break ; st[t] = true ; for (int j = 1 ;j<=n;j++){ dist[j] = min (dist[j],dist[t]+g[t][j]); } } if (dist[n] == 0x3f3f3f3f ){ return -1 ; }else { return dist[n]; } } int main () { scanf ("%d%d" ,&m,&n); memset (g,0x3f ,sizeof g); while (m--){ int a,b,c; scanf ("%d%d%d" ,&a,&b,&c); g[a][b] = min (g[a][b],c); } int t = dijkstra(); printf ("%d\n" ,t); return 0 ; }
堆优化的dijkstra算法 堆有两种实现方式,第一种是手写堆(前面有讲过),第二种方式是使用优先队列。priority_queue。 优先队列不支持修改堆中元素,因此队列中的元素个数多于node个。 稀疏图,将存储方式改成邻接表的形式。 类似于宽搜。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #include <iostream> #include <cstring> #include <algorithm> #include <queue> using namespace std ;using pair<int ,int > = PII;const int N = 100010 ;int n,m;int h[N],w[N],e[N],ne[N],idx;int dist[N];bool st[N];void add (int a,int b,int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a] h[a] = idx++; } int dijkstra () { memset (dist,0x3f ,sizeof dist); dist[1 ] = 0 ; priority_queue<PII,vector <PII>,greater<PII>> heap; heap.push({0 ,1 }); while (heap.size ()){ auto t = heap.top(); heap.pop(); int ver = t.second(),distance = t.first(); if (st[ver]) continue ; for (int i = h[ver];i!=-1 ;i = ne[i]){ int j = e[i]; if (dist[j]>dist[t]+w[i]){ dist[j] = distance+w[i]; heap.push({dist[j],j}); } } } if (dist[n] == 0x3f3f3f3f ){ return -1 ; }else { return dist[n]; } } int main () { scanf ("%d%d" ,&m,&n); memset (h,-1 ,sizeof h); while (m--){ int a,b,c; scanf ("%d%d%d" ,&a,&b,&c); add(a,b,c); } int t = dijkstra(); printf ("%d\n" ,t); return 0 ; }
Bellman-Ford算法 BF算法存边直接定义一个结构体,a,b,w就可以,不需要邻接表,临界矩阵。 BF算法运行完毕后保证dist[b]<=dist[a]+w。BF更新的过程叫松弛操作。 BF算法用于处理有负权边的问题,但是有负权回路时,最短路不一定存在。可以用BF算法求解图中是否有负权回路。 算法迭代k次的意义在于:求从1号点,经过不超过k条边,所得到的最短距离。如果迭代n次,还会更新点,就说明存在边数为n的最短路径,也就是存在负环。 算法时间复杂度,n次,m个边,O(nm)。 适用于有边数限制的最短路径。 当负环不在a和b之间时,不影响使用BF算法求解最短路径,但是SPFA算法要求图中一定不能有负环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 int n, m; int dist[N]; struct Edge // 边,a 表示出点,b 表示入点,w 表示边的权重{ int a, b, w; }edges[M]; int bellman_ford () { memset (dist, 0x3f , sizeof dist); dist[1 ] = 0 ; 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]; }
例题。 当限制了经过的边的个数,那么有负环就无所谓了。 上图表示了BF算法更新过程中出现串联的结果,如果k = 1,那么在第一轮算法更新中,我们用第一条边dist2 = 1,然后再用第二条边,dist3 = 2(因为此时dist2已经更新过了),所以为了避免不符合dist中边数的限制,我们在本轮更新中,只使用上一轮得到的结果,即使用的是上一轮的备份,这也是我们需要在i每次更新前对dist数组进行备份的原因。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include <iostream> #include <cstring> #include <algorithm> using namespace std ;const int N = 510 ,M = 100010 ;int n,m;int dist[N],backcup[N];struct Edge { int a,b,w; }edges[M]; int bellman_ford () { memset (dist, 0x3f , sizeof dist); dist[1 ] = 0 ; for (int i = 0 ;i<k;i++){ memcpy (backup,dist,sizeof dist); for (int j = 0 ;j<m;j++){ int a = edges[j].a,b = edges[j].b,w = edges[j].w; dist[b] = min (dist[b],backup[a]+w); } } if (dist[n]>0x3f3f3f3f /2 ){ return -1 ; } } int main () { scanf ("%d%d%d" ,&m,&n,&k); for (int i = 0 ;i<m;i++){ int a,b,c; scanf ("%d%d%d" ,&a,&b,&c); edges[i] = {a,b,w}; } int t = bellman_ford(); if (t == -1 ){ cout <<"impossible" <<endl ; }else { cout <<t<<endl ; } return 0 ; }
spfa 算法(队列优化的Bellman-Ford算法) 只有a变小了,b才会变小,因此我们用一个队列,专门来存储变小过的a,然后以此为根据来更新变小的b。 spfa算法伪代码如下: queue中的点就是待更新的点。只有前面的a点变小了,后面的点才有可能会需要更新。不一定要用队列,也可以用堆等等,一般用队列。 非常类似于dijkstra。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 int n; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; 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]) { q.push(j); st[j] = true ; } } } } if (dist[n] == 0x3f3f3f3f ) return -1 ; return dist[n]; }
关键改动。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 cnt[N]; int spfa () { memset (dist,0x3f ,sizeof dist); dist[1 ] = 0 ; queue <int >q; q.push(1 ); for (int i = 1 ;i<=n;i++){ st[i] = true ; q.push(i); } st[1 ] = true ; while (q.size ()){ int 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 ; } if (!st[j]){ q.push(j); st[j] = true ; } } } } if (dist[n] == 0x3f3f3f3f ) return -1 ; else return dist[n]; return false ; }
spfa判断图中是否存在负环。原理是抽屉原理。 dist[x]表示的是1到x的最短距离。 cnt[x]表示的是边数。 更新方式如下图: 如果cnt[x]>=n,就意味着从1到x至少经过了n条边,也就意味着经过了n+1个点,也就意味着存在两个点的值是相同的。也就意味着路径中存在一个环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 int n; int h[N], w[N], e[N], ne[N], idx; int dist[N], cnt[N]; bool st[N]; bool spfa () { 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 ; if (!st[j]) { q.push(j); st[j] = true ; } } } } return false ; }
在实现过程中注意h的初始化,ne的初始化,idx的初始化,cnt的初始化,dist的初始化,vt的初始化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #include <iostream> #include <cstring> #include <queue> #define N 2020 #define num_dege 6010 using namespace std ;queue <int >que;int vt[N], dist[N];int T;int h[N], e[num_dege], ne[num_dege], w[num_dege],idx;int cnt[num_dege];int n, m;void add (int a, int b, int w) { e[idx] = b; ::w[idx] = w; ne[idx] = h[a]; h[a] = idx++; } bool spfa () { memset (dist, 0x3f , sizeof dist); vt[1 ] = true ; dist[1 ] = 0 ; que.push(1 ); while (!que.empty()) { int t = que.front(); que.pop(); vt[t] = 0 ; 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 ; } if (!vt[j]) { que.push(j); vt[j] = true ; } } } } return false ; } int main () { cin >> T; while (T--) { memset (ne, -1 , sizeof ne); memset (h, -1 , sizeof h); memset (vt, 0 , sizeof vt); memset (cnt, 0 , sizeof cnt); idx = 0 ; cin >> n >> m; int a, b, w; for (int i = 0 ; i < m; i++) { cin >> a >> b >> w; if (w >= 0 ) { add(a, b, w); add(b, a, w); } else { add(a, b, w); } } if (spfa()) { cout << "YES\n" ; } else { cout << "NO\n" ; } } return 0 ; }
floyd算法 Floyd是多源汇最短路。邻接矩阵存储所有的边。三重循环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 初始化: 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; 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]); }
原理:三维状态表示d[k,i,j]只经过1-k这些中间点,从i到达j的最短距离。d[k,i,j] = d[k-1,i,k]+d[k-1,k,j]。我们发现第一维可以去掉。 例题如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <cstring> #include <iostream> #include <algorithm> using namespace std ;const int N = 210 ,INF = 1e9 ;int n,m,Q;ind d[N][N]; 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]) } } } } int main(){ scanf ("%d %d %d" ,&n,&m,&Q); 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; } } while (m--){ int a,b,w; scanf ("%d%d%d" ,&a,&b,&w); d[a][b] = min (d[a][b],w); } floyd(); while (Q--){ int a,b; scanf ("%d%d" ,&a,&b); if (d[a][b] > INF/2 ) cout <<"impossible" <<endl ; else printf ("%d" ,d[a][b]); } return 0 ; }
朴素版prim算法 最小生成树对应的是无向图。 如果是稠密图则使用朴素版的Prim算法,如果是稀疏图,则使用kruskal算法。堆优化版本的prim算法不常用。 染色法就是DFS。匈牙利算法用于求解二分图的最大匹配。 prim算法类似于dijkstra。 算法思路如下: A点所有连向集合内部中点的边的最小值,称为点到集合的距离。在生成树中选择的边就是这个最小距离。 在最小生成树的问题中,边的正负都没有问题。 集合指的是当前已经在连通块中的所有点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 int n; int g[N][N]; int dist[N]; bool st[N]; 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; }
cost先累加,再更新。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include <iostream> #include <cstring> #include <algorithm> using namespace std ;const int N = 530 ,INF = 0x3f3f3f3f ;int n,m;int g[N][N];int dist[N];bool st[N];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]; } for (int j = 1 ;j<n;j++){ dist[j] = min (dist[j],g[t][j]) } st[t] = true ; } return res; } int main () { scanf ("%d %d" ,&m,&n); memset (g,0x3f sizeof g); while (m--){ int a,b,c; scanf ("%d%d%d" ,&a,&b,&c); g[a][b] = g[b][a] = min (g[a][b],c); } int t = prim(); if (t == INF) cout <<"不存在生成树" ; else cout <<t; }
Kruskal算法 算法思路如下: 特点:不需要特殊的方式存图,只需要简单开个结构体就可以。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 int 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; }
例题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <iostream> #include <algorithm> using namespace std ;const int N = 200010 ;int n,m;int p[N];struct Edge { int a,b,w; bool operator <(const Edge &w) const { return w<w.w; } }edges[N]; int find (int x) { if (p[x]!=x){ x = find (p[x]); } return p[x]; } int main () { scanf ("%d%d" ,&m,&n); for (int i = 0 ;i<m;i++){ int a,b,w; scanf ("%d%d%d" ,&a,&b,&w); edges[i] = {a,b,w}; } sort(edges,edges+m); for (int i = 1 ;i<=n;i++){ p[i] = i; } 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 = res +w; cnt++; } } if (cnt<n-1 ) cout <<"不连通" <<endl ; else cout <<res<<endl ; }