原文链接：http://www.cnblogs.com/ACAC/archive/2010/05/24/1743142.html2007-07-15 15:48 -------------------------------------算法简述----------------------------------------- ST算法O(nlogn)预处理,O(1)的查询指定区间的最值(以最小值为例) 基本上是把待求区间[l,r]分为两段长为len的区间 左边一段为[l,l+len-1],右边一段为[r-len+1,r] len必须使得两段区间覆盖待求区间 设所求数组为w 那么,所求最小值就是两个区间的最小...
原文链接：http://www.cnblogs.com/ACAC/archive/2010/05/18/1738719.html#include <iostream>#include <queue>#define msize 1024 //最大顶点数目using namespace std; int d[msize]; //标号int r[msize][msize]; //残留网络，初始为原图int num[msize]; //num[i]表示标号为i的顶点数有多少int pre[msize];int n,m,s,t; //m个顶点，n条边，从源点s到汇点t void ini_d() //BFS计算标号，汇点...
题目背景本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。题目描述如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。输入格式第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。 接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。输出格式一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的...
https://www.cnblogs.com/sdzwyq/p/9900650.html 模板： unordered_map<int, int> mp; LL q_pow(LL n, LL k, LL p) {LL ans = 1;if(k == -1) return 0;while(k) {if(k&1) ans = (ans*n) % p;n = (n*n) % p;k >>= 1;}return ans; } int BSGS(int a, int b, int p){int m = sqrt(p)+1, s = b;for(int i = 0; i < m; ++i){mp[s]=i;s= (s*1LL*a)%p;}int t = q_pow(a, m, p);s = 1;for(int i = 1; i <= m; ++i){s = (s*1LL*t)%p;if(mp.f...
首先明白匈牙利算法是干什么的？ 就是从二分图中找出最多一对一的数量。（最大匹配） 这里有几个概念： 二分图： 二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。 简单的说，一个图被分成了两部分，相同的部分没有边，那这个图就是二分图，二分图...
#include<stdio.h> #include<iostream> #include<string> #include<string.h> #include<map> using namespace std;???? const int N = 510; bool line[N][N],used[N]; int link[N]; int n, m, nn, mm; bool find(int x) { ????for (int i = 1; i <= 53; i++) ????{ ????????if (line[x][i] == true && used[i] == false) ????????{ ????????????used[i] = true; ????????????if (link[i] == -1 || find(link[i])) ????????????{ ??...
地杰斯特拉算法步骤： 1.找离起点x最近的未讨论过的点k 2.判断经过k点，起点x到其他点的距离是否缩短，如缩短则更新。将k点标记为已讨论。 3.返回第1步，直到所有点都被讨论过 O（n^2）: #include<bits/stdc++.h> using namespace std; int map1[101][101],dis[101],n,m; bool mark[101]; void dij(int x) {int k,i,Min;for(i=1;i<=n;i++){dis[i]=map1[x][i];}mark[x]=1;//初始化do{Min=0x7f;k=0;for(i=1;i<=n;i++)步骤1{if(mark[i...
先上代码：const int maxn=100010; //字符串长度最大值 int nt[maxn],ex[maxn]; //ex数组即为extend数组 ///预处理计算next数组 void GETNEXT(char *str) {int i=0,j,po,len=strlen(str);nt[0]=len;///用自己作为后缀与自己匹配while(str[i]==str[i+1]&&i+1<len) i++;///暴力求next[1]nt[1]=i;po=1;///从此点出发next数组延伸位置最远for(i=2;i<len;i++){if(nt[i-po]< nt[po]+po-i )///第一种情况，可以直接得到next[i]的值nt[i]...
线性基 GavinZheng敲懒的。。。 menci大佬的线性基博客 模板代码引自menci： struct LinearBasis {long long a[MAXL + 1];LinearBasis(){std::fill(a, a + MAXL + 1, 0);}LinearBasis(long long *x, int n){build(x, n);}void insert(long long t){for (int j = MAXL; j >= 0; j--){if (!t) return;if (!(t & (1ll << j))) continue;if (a[j]) t ^= a[j];else{for (int k = 0; k < j; k++) if (t & (1ll << k)) t ^= a[k];for (int...
基础算法模板——排序 1. 快速排序 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 ) ; }利用快速排序找到第k小的数 int quick_sort(int q[], int l, int r, int k){if(l >=k) return q[l];int i = l - 1, j = r + 1, x =...
基础算法模板——前缀和与差分 1. 前缀和 #include <iostream>using namespace std;const int N = 100010;int n, m; int a[N], s[N];int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化while (m -- ){int l, r;scanf("%d%d", &l, &r);printf("%d\n", s[r] - s[l - 1]); // 区间和的计算}return 0; }2. 子矩阵的和（...
基础算法模板——高精度运算 1. 高精度加法 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; }2. 高精度减法 #include <iostream> #include <vector>using namespace std;bool cmp(vector<int> &A, vector<int>...
[算法模板]Kruskal重构树 kruskal重构树是一个很常用的图论算法。主要用于解决u->v所有路径上最长边的最小值，就是找到\(u->v\)的一条路径，使路径上的最长边最小。 图片来自Kruskal重构树学习笔记+BZOJ3732 Network从上图我们可以看出，kruskal重构树有以下特质：每个原图上的节点一一对应重构树上的叶子节点。 重构树上每一个其他节点（正方形）代表原图上的一个边，有点权。 重构树是一棵二叉树。 重构树是一个二叉堆。（所以两...
链接题目描述 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz 输入输出格式 输入格式： 第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000） 接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi 输出格式： 输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz 输入输出样例输入样例#1： 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3输...
[算法模板]整体二分 引子 很多题都可以用二分解决。但是如果我们对每个查询都直接二分，可能会收获一个 TLE 。这时候我们就会用到整体二分。整体二分的主体思路就是把多个查询一起解决。（所以这是一个离线算法）所谓整体二分，需要数据结构题满足一下性质：询问的答案具有可二分性 修改对判定答案的贡献互相独立，修改之间互不影响效果 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值 贡献满足交换律，结合律，具...