什么是最小树形图？相信大家如果会过来看这篇文章，想必也应该对最小生成树有所了解的，最小生成树求的是无向图的一颗生成树的最小权值。我们的最小树形图就是来解决一个有向图的一颗生成树的最小权值，对于度娘来说，最小树形图是这样定义的：最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。通解最小树形图的一种算法是是1965年朱永津和刘振宏提出的复杂度为O(...
算法模板汇总1、牛顿迭代法(c++代码)int mysqrt(int x){double tmps = x;double k = 1.0;double k0 = 0.0;while(abs(k0-k) >= 1){k0 = k;k = (k + tmpx/k)/2;}return (int)k; } 2、二分查找代码模板left, right = 0, len(array) - 1 while left <= right:mid = (left + right) / 2if array[mid] == target:#find the target!!breakorreturn resultelif array[mid] < target:left = mid + 1else:right = mid + 1 3、递归代码模板def...
1.归并排序板子（包含求逆序对个数）：#include<bits/stdc++.h> usingnamespace std; constint maxn=1e5+10; int a[maxn],tmp[maxn]; int ans=0;void merge_sort(int l,int r) {if(l>=r)return;int mid=l+r>>1;merge_sort(l,mid);merge_sort(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(a[i]<=a[j])tmp[k++]=a[i++];else{ans+=mid-i+1;tmp[k++]=a[j++];}}while(i<=mid)tmp[k++]=a[i++];while(j<=r)tmp[k++]=a[j++];for(i...
详解：http://blog.csdn.net/wall_f/article/details/8207595算法时间复杂度：O（E * V * V） 1 #include <cstdio>2 #include <cstring>3 #include <queue>4 #include <vector>5usingnamespace std;6#define N 1057#define M 10108#define INF 0x3f3f3f3f910struct Edge { 11int u, v, cap; 12 Edge () {} 13 Edge (int u, int v, int cap) : u (u), v (v), cap (cap) {} 14 }edge[N*N]; 15 vector<int> G[N]; 16int S, T, ...
1 #include <stdio.h>2 #include <string.h>3 #include <algorithm>4usingnamespace std;5constint N=1001;6constint inf=1<<29;7int w[N][N];8int dis[N],flag[N];9int n,m,u,v,c; 10int prim() 11{ 12int sum=0;//计算最小距离13 memset(flag,0,sizeof(flag)); 14for(int i=1; i<=n; i++) 15 { 16 dis[i]=w[1][i];//把起点到每个点的距离付给dis17 } 18 flag[1]=1; 19for(int i=1; i<n; i++)//会更新n-1次...
一、为什么要有模板？将类型参数化，可以实现算法与类型的分离，编写针对类型更加抽象的函数或者类。 二、函数模板通用定义：template<typename 类型形参1, ...>返回类型 函数模板名 (形参表) { ... }特化定义：template<>返回类型 函数模板名<类型实参1, ...> (形参表) { ... } 三、类模板通用定义：template<typename 类型形参1, ...>class 类模板名 { ... };全类特化：template<>class 类模板名<类型实参1, ...> { ... };成员特...
该模板来自大白书 【解释】给多个语句，每个语句为“ Xi为真(假) 或者 Xj为真(假)”每个变量和拆成两个点 2*i为假， 2*i+1为真“Xi为真 或 Xj为真” 等价于 “Xi为假 –> Xj为真”。DFS算法没有回溯过程。 【函数说明】模板bfs函数在模板外一般用不到void init(int n) :初始化void add(int x,int xval,int y,int yval) :添加边，x,y为节点编号，xval=1表示真，xval=0表示假，yval同理bool solve() :计算是否存在解。如果存在解返...
模板—算法—整体二分（区间k小值）Code:#include <cstdio> #include <algorithm> using namespace std; #define N 200010 int num[N],number[N],tmp[N],ans[N],n,m,id[N]; struct Ask {int l,r,id,k;}ask[N],ask1[N],ask2[N]; void change(int x,int y) {while(x<=n) tmp[x]+=y,x+=x&-x;} int find(int x) {int sum=0;while(x) sum+=tmp[x],x-=x&-x;return sum;} bool cmp(const int &a,const int &b) {return num[a]<num[b];} in...
#include<iostream> #include<algorithm>usingnamespace std;int f[20000],n;struct node {int u,v,val;booloperator < (node&a) const{return val<a.val;} }e[20000];int findx(int x) {if(x==f[x])return x;return f[x]=findx(f[x]); } int main() {int k,ans,x,y;while(cin>>n){ans=0;k=(n*(n-1))/2;for(int i=1;i<=n;i++)f[i]=i;for(int i=0;i<k;i++)cin>>e[i].u>>e[i].v>>e[i].val;sort(e,e+k);for(int i=0;i<k;i++){x=findx(...
#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...