1 jinli_

尚未进行身份认证

暂无相关简介

等级
TA的排名 32w+

ACM算法blog与模板合集(逐步完善中)

数据结构LCA&&树链剖分:LCA是用来求最近公共祖先的算法树链剖分可以快速求出树上两点之间的信息https://blog.csdn.net/enjoy_pascal/article/details/78277008树上启发式合并(dsuontree):可以统计各个结点为根的子树的信息https://blog.csdn.net/qq_40791842/articl...

2019-07-14 21:38:16

组合数

求解组合数1.根据二项式定理,求出1~n的所有c(i,k):c[i][j]的意思为从i中选择j个出来时间复杂度O(n^2);memset(C,0,sizeof(C));for(int i=0;i<=n;i++){ C[i][0]=1; for(int j=1;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];}2.递推求出c...

2019-04-02 12:35:18

线性规划之单纯形法

https://www.hrwhisper.me/introduction-to-simplex-algorithm/#comments看看能不能取得博主的许可,做个搬运工hud的板子:n个约束条件,m个未知数求目标函数最大值const int maxn=1810,maxm=610,inf=!0U>>2;int n,m,a[maxn][maxm],nxt[maxm];vo...

2019-03-30 23:11:29

高斯消元

高斯消元高斯消元是一个求解多元一次方程组的方法https://blog.csdn.net/pengwill97/article/details/77200372高斯消元模板#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h&gt...

2019-03-29 20:48:55

欧拉定理&&费马小定理

欧拉定理下面为欧拉定理的扩展欧拉定理可进行欧拉降幂:若gcd(a,p)=1;a ^ b mod p = a ^ ( b % phi§ + phi§ ) (mod p)由于欧拉函数很快就能降为1,所以递归几次即可快速得出答案。可做这题https://cn.vjudge.net/problem/14888/originac代码#include<math.h>#in...

2019-03-24 00:46:04

AC自动机

题目HDU - 4787ac代码#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>#include <string>#include <vector>#incl...

2019-03-23 21:21:27

差分约束

题目 HYSBZ - 2330AC代码#include<stdio.h>#include<algorithm>#include<string.h>#include<vector>#include<queue>#include<stdlib.h>using namespace std;struct edge{...

2019-03-19 20:27:21

K短路

题目 LightOJ - 1099AC代码#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>#include<queue>using namespace std;typedef pair<int,int>P;con...

2019-03-19 20:16:06

Meet in the middle

题目 POJ - 1903AC代码#include<stdio.h>#include<iostream>#include<string.h>#include<stdlib.h>#include<map>#include<algorithm>using namespace std;const int maxn...

2019-03-19 20:10:24

回滚莫队

题目 SPOJ - ZQUERY#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<algorithm>using namespace std;const int INF=0x3f3f3f3f;int a[50005],...

2019-03-19 20:04:13

二分图匹配——匈牙利算法&&KM算法

二分图1.1何为二分图二分图是指可以把结点集分成两部分X和Y,使得每条边恰好一个端点在X,另一个端点在Y1.2二分图匹配完美匹配:每个点都被匹配到完备匹配:二分图中X中的每一个顶点都与Y部中的一个顶点匹配,或者Y部中的每一个顶点也与X部中的一个顶点匹配,则该匹配为完备匹配。2.二分图的最大基数匹配,主要针对无权图,需要求出包含边数最多的匹配;可用前面介绍的Edmonds-Karp||D...

2019-03-14 23:45:11

最大流问题——Edmonds-Karp&&Dinic算法模板

Edmonds-Karp算法简介Edmonds-Karp算法使用BFS不断寻找增广路,直到没有增广路存在,则为最大流Edmonds-Karp算法模板时间复杂度为O(nm^2)struct edge{ //储存边 int from,to,flow,cap; edge(int u,int v,int f,int c):from(u),to(v),flow(f),cap(c){}}...

2019-03-14 22:58:01

链式前向星模板

什么是链式前向星链式前向星实际上是储存邻接表的一种数据结构。跟vectorg[maxn]用途一样。那为什么不直接用vectorg[maxn]呢?在有些时候,用vectorg[maxn]会造成超时(使用stl普遍比较耗时)。这时候,就可以用链式前向星。链式前向星模板int tot; //存储的边数(初始化为0)int head[maxn]; //head[i]存储结点i的第一条边(初...

2019-03-14 20:57:16

最短路问题——Floyd算法模板

Floyd算法简介Floyd算法计算的是每两点之间的最短路,既可用于计算正权路,又可计算负权路Floyd算法模板时间复杂度为O(n^3)const int INF=1<<30;int d[maxn][maxn];void Floyd(){ for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j...

2019-03-14 20:23:07

最短路问题——Bellman-Ford与Spfa算法模板

Bellman-Ford和Spfa算法简介用来求负权路的单源最短路问题,若是存在负权环,则不存在最短路。Bellman-Ford算法模板时间复杂度为O(nm)const int INF=1<<30;for(int i=0;i<n;i++) d[i]=INF;d[0]=0;for(int k=0;k<n-1;k++) //迭代n-1 for(int i=0;...

2019-03-14 20:13:36

最短路问题——Dijkstra算法模板

Dijkstra算法简介Dijkstra算法主要用来解决边权为正时的单源最短路问题(就是从一个源点出发,到所有结点的最短路),同时适用于有向图和无向图Dijkstra算法思路略Dijkstra算法模板时间复杂度为O(n^2)没有堆优化的代码时间复杂度为O(n^2)const int INF=1<<30; int v[maxn];int d[maxn];int w[...

2019-03-14 19:49:03

最小生成树——Prime算法模板

Prime算法思路1.我们先设两个顶点集合,一个为加入最小生成树的顶点集合X,另一个为未加入最小生成树的顶点集合Y2.如果X中没有结点,选任意一个结点将其放入X中,接下来重复下面的过程:从X中找到关联权值最小的边且这条边的另一个结点在Y中,将该结点加入X中。直到有n个结点处于X中(既Y中无结点),则停止寻找。3.得到的图则为最小生成树Prime算法用于稠密图时效率更高Prime算法模板...

2019-03-14 19:10:18

最小生成树——Kruskal算法模板

Kruskal算法的思路1.先将所有边按照权值从小到大排序2.然后从小到大枚举每条边(u,v)3.接下来会出现两种情况:情况1:u和v在同一个连通分量中,加入(u,v)后会形成环,不可以选这条边(后面加入的边权值一定比前面加入的使u和v连通的边的权值大,所以放弃加入当前这条边)情况2:如果u和v在不同的连通分量,则加入(u,v)(若不加这条边,后面加入的使u和v连通的边权值一定比当前边大...

2019-03-14 18:21:25
勋章 我的勋章
    暂无奖章