#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
usingnamespace std;constint maxn=1111;//有多少个结点
vector<int>G[maxn];
int visited[maxn];//标记该节点有没有访问过int node,edge;//顶点数目int tmpdfn;//dfs过程中记录当前的深度优先搜索序数int dfn[maxn];//记录每个顶点的深度优先搜索序数int low[maxn];//每个顶点的low值，根据该值来判断是否是关节点int son;//根结点的有...
一.引入二分图匹配算法是一个非常有用的算法，我们首先从一个简单的题目引入。给你n个水果，m个箱子，每个水果只能被放在指定的几个箱子里，每个盒子只能放一个水果，问如何安排能使的放在盒子里的水果最多。怎么写？暴力，可以试试。但不管是暴力还是什么算法，都需要面对一个情况——后面的水果如果没盒子放了，不能不管不顾，应该腾空间。对，腾。二分图算法的最重要思想就是腾二.算法流程二分图有两种主流算法，一个是匈牙利算...
1.Dijkstra算法（计算正权图上的单源最短路 single-source shortest paths (sssp) ）从单个节点出发到所有节点的最短路。该算法适用于：有向图和无向图。1). O(n^2)的实现：邻接矩阵map存储实现，INF表示无穷大void Dijkstra(int s, int e, int n) //从s开始到e点的最短路，有n个节点，编号：0-->n-1.
{memset(vis, 0, sizeof(vis));int i, j;for(i=0; i<n; i++)dis[i]=(i==0?0:INF);for(i=0; i<n; i++){int mm=INF; int pos;for...
Sunday是一个线性字符串模式匹配算法。算法的概念如下：Sunday算法是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。其核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。记模式串为S，子串为T，长度分别为N，M。对于T，我们做一个简单而巧妙的预处理：记录T中每一种字符最后出现的位置，将其...
pair的常见用法pair是一个很实用的“小玩意”，当想要将两个元素绑在一起作为一个合成元素、又不想要因此定义结构体时，使用pair可以很方便地作为一个代替品。也就是说，pair实际上可以看作一个内部有 两个元素的结构体，且这两个元素的类型是可以指定的，如下面的短代码所示：struct pair{typeName1 first;typeName2 second;
}
pair的定义头文件#include<utility>
using namespace std;
因为实现map时候已经使用了pair，所以...
算法第四版第二章排序需要复用的代码的模板。其中 algs4 是算法这本书作者自己写的一个类库，包含了一些常用的简单的方法。ps : less()比较大小的方法 exch()交换两个变量的值的方法 show()向控制台输出结果的方法 isSorted()测试数组元素是否有序的方法 1import java.util.Scanner;2 3import edu.princeton.cs.algs4.In;4 5publicclass Example {6publicstaticvoid sort(Comparable[] a){7 }8privatestaticboolean le...
自己对Dijstra算法的理解是：首先输入保存点，边的权值（注意无向图和有向图在保存时的区别）。将表示从起点st到顶点 i 的距离的d[ i ]数组的每一个值初始化为INF，令d[st] = 0。 遍历d[ ]数组的下标 i （即顶点 i）这个操作是通过优先队列来实现的，然后遍历以顶点 i 为起点的边，更新d[ i ]的最小值。最后直接访问d[en]，即可得到最短距离。通过模板题来熟悉一下这个算法吧，最短路之HDU2544 1 #include <iostream>2 #include <c...
Manacher算法能够在O(N)的时间复杂度内得到一个字符串以任意位置为中心的回文子串。其算法的基本原理就是利用已知回文串的左半部分来推导右半部分。例题：HDU 3068 1 #include<stdio.h>2 #include<string.h>3 #include<iostream>4usingnamespace std;5constint N=110005;6char s[N],cpy[N<<1];7int rad[N<<1];8void manacher(char *s,int len,int rad[])9{
10for(int i=1,j=0,k;i<len;i+=k)
11 {
12while(s[i-j-1]==s[i+j+1]) ...
算法基础课相关代码模板活动链接 —— 算法基础课快速排序算法模板 —— 模板题 AcWing 785. 快速排序 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);}归并排序算法模板 —— 模板题 AcWing 787. 归并排序void m...
/*INPUT6
10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6OUTPUT15*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
usingnamespace std;
constint N=1e5;
struct node
{int u,v,w;booloperator<(const node &C)const{return w<C.w;//表示以w从小到大排序 }
}t[N];
int n,m;
int p[1001];
int cha(int x)
{//return x==p[x]?p[x]:cha(p[x]);if(x!=p[x]){p[x]=cha(p[x]);/...
a*x+b*y=gcd(a,b)，该方程一定有解（原因暂时留坑，以后来填），扩展欧基里德算法就是用来求x，y的。 具体求法，因为a*x+b*y=gcd(a,b)，而gcd(a,b)=gcd(b,a%b)，所以有b*x1+(a%b)*y1=gcd(a,b)，而a%b=a-(a/b)*b，代入之后得：a*y1+(x1-(a/b)*y1)*b=gcd(a,b)，即x=y1,y=x1-(a/b)*y1，这样用递归就可以实现了。 扩展欧基里德算法的模板：1void ex_gcd(int a,int b,int &x,int &y,int &d){
2if(!b) x=1,y=0,d=a;
3else{ex_gcd(b...
[算法模板]FFT-快速傅里叶变换感谢ZYW聚聚为我们讲解FFT~思路我懒，思路和证明部分直接贴链接：rvalueLSJ-FFT与NTT基础代码主要思想是利用了单位根特殊的性质（n次单位根后一半幂跟前一半幂取值相等）。只是因为式子中奇数次幂还要提出来个\(\omega_n^k\)，这个东西只要取个反就好了（即对称性：\(\omega_n^k=-\omega_n^{k+\frac{n}{2}}\)）。FFT递归：#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=2e...
1/* 2 algorithm : High-Precision FFT3 4*/ 5 #include <cstdio>6 #include <cstring>7 #include <cmath>8 #include <algorithm>9#define N 20000510#define pi acos(-1.0) // PI值 11usingnamespace std;12struct complex13{14double r,i;15 complex(double real=0.0,double image=0.0){16 r=real; i=image;17 }18// 以下为三种虚数运算的定义 19 complex operator + (const complex o){20return compl...
ps：数组下标从0开始哦！①求逆序对版int tmp[MAX],rec[MAX];
int sum;//求逆序对个数 void merge(int low,int mid,int high)
{int i=low,j=mid+1,k=low;while(i<=mid&&j<=high){if(rec[i]>rec[j]) {tmp[k++]=rec[j++];sum+=mid-i+1;}else tmp[k++]=rec[i++];}while(i<=mid) tmp[k++]=rec[i++];while(j<=high) tmp[k++]=rec[j++];for(i=low;i<=high;i++) rec[i]=tmp[i];
}
void mergesort(int low,int high)
{if(low<high){int mi...
实现功能：求出二维平面内一对散点的凸包（详见Codevs 1298）很神奇的算法——先将各个点按坐标排序，然后像我们所知的那样一路左转，求出半边的凸包，然后反过来求另一半的凸包我以前正是因为总抱着想一步到位的想法，所以每次都跪得很惨（HansBug：事实上这次是我这辈子第一次A掉凸包题）然后别的没了，就是凸包的基本思想（顺便输出凸包周长C和面积S，好评如潮哦） 1type arr=array[0..100005] of longint;2var 3 i,j,k,l,m,n...
原文链接：bestsort.cn