(完整word版)2018noip复赛资料

1、Sort() 排序 三个参数， 例 1 ： int a10; sort(a,a+5); 从 a0到 a4排序 例 2 ： bool cmp(asd a,asd b) if() return true; return flase; asd a10; sort(a,a+5,cmp);用 cmp 规则排序 next_permutation () 定义在 里面。 参数为迭代器，可以理解为地址，对数组 a 全排列为 next_permutation(a,a+n); 需排参数可是任意类型，按字典序排列，默认由小到大。 若可生成下一个全排列，返回true，否则返回false。 该函数为生成下一个递增排列。若

2、输出全排列，需对原数组排序。 prev_permutation() 为上一个排列。 该函数的第三个参数可为自定义标准，由此可对结构体中的某个元素进行全排列。与sort()用法相似。 广度优先遍历 广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些 结点中第一个邻接点的所有结点，重复此方法，直到所有结点都被访问完为止。 用邻接矩阵或邻接表记录图，通过队列遍历。定义一个结构体，x表示节点，丨表示广度，队列里存放结构体变量，依次 取出并搜其能到达的节点。将其放入队列直至符合要求。 深度优先遍历 深度优先搜索的主要思想是：首先以一个未被访问过的顶点

3、为起始顶点，沿当前顶点的边走到未访问过的节点，当没有 未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的定点都被访问过。即沿着图的某一条分支 遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止。 用邻接矩阵或邻接表记录图，通过 递归遍历。若求路径则用栈存储。 函数两个变量，一个为节点，一个为深度。 宗教信仰： #include #include #include #include using namespace std; const int N=50000+5; vector GN; int visN; int n,m; void dfs(int

4、 u) if(visu=1)return; visu=1; int d=Gu.size(); for(int i=0; id; i+) int v=Gui; /if(visv=0) dfs(v); int main() int number=0; while(scanf(%d%d, for(int i=1; i=n; i+) Gi.clear();/ 清空 for(int i=1; i=m; i+) int u,v; scanf(%d%d, Gu.push_back(v); Gv.push_back(u); memset(vis,0,sizeof(vis); int cc=0; for(int

5、 u=1; u=n; u+) if(visu=0) cc+; dfs(u); number+; printf(Case %d: %dn,number,cc); return 0; 链式前向星 有权边的图的存储一般有两种：邻接矩阵(存点) 、前向星(存边)。 若图是稀疏图，边很少，开二维数组 a很浪费;若点很多(如10000个点)a1000010000又会爆.只能用前向星做 前向星的效率不是很高(要将边的起点或终点进行排序) ，优化后为链式前向星，效率有所提升。 1 结构体数组 edge 存边， edgei 表示第 i 条边 , 2 headi存以i为起点的第一条边(在edge中的下标) 增边：

6、若以点i为起点的边新增了一条，在edge中的下标为j. 那么 edgej.next=headi; 然后 headi=j. edge 即每次新加的边作为从该起点出发的第一条边， 最后倒序遍历(即 edgej.next 用来记录以该点为起点的下一条边在 中的下标，用于遍历) #include using namespace std; #define MAXM 500010 #define MAXN 10010 struct EDGE int next;/ 与该边同起点的下一条边的存储下标 int to;/ 这条边的终点 int w;/权值 ; EDGE edgeMAXM; int n, m, cn

7、t; int headMAXN; /headi 表示以 i 为起点的第一条边 void Add(int u, int v, int w) /起点 u, 终点 v, 权值 w edge+cnt.next = headu; edgecnt.w = w; edgecnt.to = v; headu = cnt;/ 第一条边为当前边 void Print() int st; cout st; for(int i=headst; i!=0; i=edgei.next) /i 开始为第一条边， 每次指向下一条 ( 以 0 为结束标志 ) 若下标从 0 开始， next 应初始化 -1 cout Start

8、: st endl; cout End: edgei.to endl; cout W: edgei.w endl n m; for(int i=1; i s t w; Add(s, t, w); Print(); return 0; 最短路问题 1. 弗洛伊德算法： 通过中间节点k来实现i和j的距离缩短，空间和时间复杂度都为n3, 般数据在400以内可以使用。 for(int i=0;in;i+) for(int j=0;jn;j+) for(int k=0;kn;k+) if(aikinf 2. 迪杰斯特拉算法： 指定一个点到其余各个顶点的最短路径，也叫“单源最短路径 矩阵存储边代码： in

9、t e1010,dis10,book10,n,m,t1,t2,t3,u,v,min; int inf=130; /读入n和m, n表示顶点个数，m表示边的条数 scanf(%d%d, /初始化 for(int i=1; i=n; i+) for(int j=1; j=m; j+) if(i=j) eij=0; else eij=inf; /读入边 for(int i=0; im; i+) scanf(%d%d%d, et1t2=t3; /初始化 dis 数组，这是 1 号顶点到其余各个顶点的初始化路程 for(int i=1; i=n; i+) disi=e1i; /book 数组初始化 fo

10、r(int i=1; i=n; i+) booki=0; book1=1; /核心算法 for(int i=1; i=n-1; i+) /找到离 1 号点最近的顶点 min=inf; for(int j=1; j=n; j+) if(bookj=0 u=j; booku=1; for(int v=1; v=n; v+) if(euvdisu+euv) disv=disu+euv; /输出结果 for(int i=1; i=n; i+) printf(%d ,disi); 链式前向星存储边： #include #include #include #include #include using n

11、amespace std; struct EDGE int next; / 下一条边的存储下标 int to; / 这条边的终点 int w; / 权值 ; EDGE edge100; int n, m, cnt; int head10; /headi 表示以 i 为起点的第一条边 void Add(int u, int v, int w) / 起点 u, 终点 v, 权值 w edge+cnt.next = headu; edgecnt.w = w; edgecnt.to = v; headu = cnt; / 第一条边为当前边 int main() int dis10,book10,t1,

12、t2,t3,u,v,min; int inf=130; /读入n和m, n表示顶点个数，m表示边的条数 scanf(%d%d, /读入边 for(int i=0; im; i+) scanf(%d%d%d, Add(t1,t2,t3); /初始化 dis 数组，这是 1 号顶点到其余各个顶点的初始化路程 for(int i=1; i=n; i+) disi=inf; dis1=0; for(int i=head1; i!=0; i=edgei.next) disedgei.to=edgei.w; /book 数组初始化 for(int i=1; i=n; i+) booki=0; book1=

13、1; /核心算法 for(int i=1; i=n-1; i+) /找到离 1 号点最近的顶点 min=inf; for(int j=1; j=n; j+) if(bookj=0 /输出结果 for(int i=1; i=n; i+) printf(%d ,disi); return 0; /* 输入 6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4 输出 0 1 8 4 13 17 */ 3. bellman-ford 算法 核心代码： for( int k=1;k=n;k+) for(int i=1;idisui+wi

14、) disvi=disui+wi; i 条边存储在 ui vi wi 中，表示从顶点 U,并且用U点当前的最短路径估计值对 且 v点不在当前的队列中，就将v点放 dis 数组作用与迪杰斯特拉算法相同。u、v、w 三个数组用来记录边的信息。第 ui到到顶点vi的边权值为wi. 4.SPFA 算法 设立一个先进先出的队列 q 用来保存待优化的结点，优化时每次取出队首结点 离开U点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整, 入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 代码示例： void spfa(int s) for(int i=0; i=n; i+) d

15、isi=99999999; / 初始化每点 i 到 s 的距离 diss=O; viss=1; q.push(s);/队列初始化,s为起点，dis数组作用与bellman-ford算法相同 int i, v; while (!q.empty()队列非空 v=q.front();取队首元素 visv=O;/释放队首结点，因为这节点可能下次用来松弛其它节点，重新入队 for(i=0; i0 修改最短路 if (visi=0)如果扩展结点i不在队列中，入队 q.push(i); visi=1; 最小生成树(kruskal算法) 此算法可以称为“加边法”，初始最小生成树边数为0,每迭代一次就选择一条满

16、足条件的最小代价边，加入到最小生成 树的边集合里。 1. 把图中的所有边按代价从小到大排序； 2. 把图中的n个顶点看成独立的n棵树组成的森林； 3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi ,应属于两颗不同的树，则成为最小生成树的一条边，并 将这两颗树合并作为一颗树。 4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。 #include using namespace std; struct Edge int u,v,w; edge200005; int fa5005,n,m,ans,eu,ev,cnt; inline bool cmp(Edge a,

17、Edge b) return a.wb.w; / 快排的依据 inline int find(int x) while(x!=fax) x=fax=fafa x; return x; /并查集模板，用while循环比递归版快 inline void kruskal() sort(edge,edge+m,cmp); 将 边的权值排序 for(int i=0; im; i+) eu=find(edgei.u), ev=find(edgei.v); if(eu=ev) continue;/ 若出现环，贝U continue ans+=edgei.w; 更新答案 faev=eu; cnt+; if(cnt=n-1) break;/ 循环结束条件 int main() scanf(%d%d, for(int i=1; i=n; i+) fai=i; /初始化并查集 for(int i=0; iv，则排序时U必须在v前面。 由此可以看出一个图的拓扑排序可能不止一种，可以自己举例试一下，加深理解。 实现方法： 图的存储可以用邻接矩阵或是邻接表，排序时，定义两个队列(queue) q1，q2，先遍历一次所有的节点求出各节点的 入度，并找到入度为零的节点(即没有边指向的节点)，将其放入q1中