计算几何
计算几何
三点共线
A,B,C三点共线当且仅当AB⃗×AC⃗=0\vec{AB}\times \vec{AC}=0AB×AC=0。
给定三点坐标A(x1,y1),B(x2,y2),C(x3,y3)A(x_1,y_1),B(x_2,y_2),C(x_3,y_3)A(x1,y1),B(x2,y2),C(x3,y3)，则有AB⃗=(x2−x1,y2−y1)\vec{AB}=(x_2-x_1,y_2-y_1)AB=(x2−x1,y2−y1)，AC⃗=(x3−x1,y3−y1)\vec{AC}=(x_3-x_1,y_3-y_1)AC=(x3−x1,y3−y1)。
AB⃗×AC⃗=((x2−x1)(y3−y1)−(y2−y1)(x3−x1))\vec{AB}\times \vec{AC}=((x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1))
AB×AC=((x2−x1)(y3−y1)−(y2−y1)(x3−x1))
1234bool areCollinear(int x1, int y1, int x2, int y2, int ...
网络流问题
网络流问题
最大流
Ford-Fulkerson算法
概述
最大流问题中，我们主要关注剩余容量。在获得最后各边的剩余容量之后，只需要拿源点的初始容量减去剩余容量即可得到流量。
我们首先寻找一条能抵达汇点的路径，很容易得到该路径能输送的最大流量取决于这条路径最小容量的边。然后将这条路径加上该流量，更新剩余容量。当某条边剩余流量为0时我们将无法再通过它来输送流量，所以可以考虑将其移除，之后再寻找其他路径，直至无法抵达汇点。我们将这个过程中删除满流的边之后，边权为剩余流量的图称为残量网络。
但是这个过程中无法进行回溯，所以如果我们删除了一条不是最优的边(表示选中了它)那我们将无法放弃选择，从而得不到最优解。Ford−FulkersonFord-FulkersonFord−Fulkerson算法的关键在于，当我们在压入流量的同时在残量网络中添加容量大小与正向流量相等的反向边。
例如：对于节点v1−>v2v1->v2v1−>v2如果v1v1v1流向v2v2v2的容量为6，流量大小为5那么我们添加一条容量(剩余容量)为5的反向边(如果已经存在反向边则更新其容量)。最终不存在路径可 ...
图中的最短路径问题
图中的最短路径问题
Dijkstra算法
基本描述
主要用来解决单源最短路径问题，采用贪心策略，无法解决存在负权值的问题。
实现思路
首先设置一个集合SSS，用来存放已经确定最短路径的顶点；初始化图TTT；
将源点uuu加入集合SSS并初始化数组dis[i]表示源点到点iii的距离；初始化：dis[u]=0 dis[other]=MAX
然后从图TTT中选取一个与uuu直接相连权值最小的点vvv加入集合SSS；
对与vvv相邻的每个点xxx进行松弛操作：dis[x]=min(dis[x],dis[x]+G[v][x])
重复3 4操作直至TTT为空；
示例代码
无优化
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071struct edge{ int to; int nextEdge; int w;} e[100010];int c ...
拓扑排序
拓扑排序
概述
对一个DAGDAGDAG(有向无环图)GGG进行拓扑排序，是将GGG中所有顶点排成一个线性序列，使得图中任意一对顶点uuu和vvv，如果存在一条有向边u−>vu->vu−>v则uuu在vvv之前出现。简单来说，是在不破坏节点先后顺序的情况下，把DAGDAGDAG拉成一条链。
注意：拓扑排序可能不是唯一的。
Kahn算法
首先获取所有**入度为000**的节点，将他们排在前面然后从图中删除。此时有些点的入度会减少，重复前面的操作直到所有点都被删除(输出)。
我们可以通过BFSBFSBFS来实现，使用一个队列，首先遍历入度为0的节点(这些节点入队)，队首出队，与队首所连节点度数−1-1−1，如果有节点度数减为0将其加入队列，重复上述操作直至队列为空。
示例代码
1234567891011121314151617181920212223242526272829303132333435struct edge{ int to;//指向的节点 int NextE;//下一条边} e[100];int num_e = 0;//边数int hea ...
图的表示
图的表示
邻接矩阵
使用graph[i][j]>0graph[i][j]>0graph[i][j]>0表示顶点iii与jjj之间存在一条边，graph[i][j]graph[i][j]graph[i][j]的值可以表示边的权值。
12345678910void getGraph(int n, int m){ for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u][v] = 1; //无向图graph[v][u] = 1; }}
邻接表
数组模拟
使用graph[i][0]graph[i][0]graph[i][0]表示和顶点iii相连的点有多少个，graph[i][j]graph[i][j]graph[i][j]表示第jjj个与iii相连的点的编号。例如graph[2][0]=5graph[2][0]=5graph[2][0]=5表示与222号顶点相连的点 ...
图的DFS和BFS
图DFS和BFS
题目描述
小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。
假设洛谷博客里面一共有 n(n≤105)n(n\le10^5)n(n≤105) 篇文章（编号为 1 到 nnn）以及 m(m≤106)m(m\le10^6)m(m≤106) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。
输入格式
共 m+1m+1m+1 行，第 1 行为 2 个数，nnn 和 mmm，分别表示一共有 n(n≤105)n(n\le10^5)n(n≤10 ...
