最小生成树
最小生成树
一个有nnn个顶点的图，边个数一定大于等于n−1n-1n−1。图的最小生成树指的是在这些边中选择n−1n-1n−1条边，形成一棵包含所有顶点的树，这n−1n-1n−1条边的权值之和在所有方案中最小。
Prim算法
基本描述
PrimPrimPrim算法从点出发，每次选择与已加入节点距离最小的节点。时间复杂度为O(n2+m)O(n^2+m)O(n2+m)一般在稠密图中使用。
代码实现
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include <bits/stdc++.h>using namespace std;#define Max 200000010int graph[5050][5050];long long Prim(int n){ int vis[5050] = {0}; ...
C5-D
C5-D 外接圆
题目描述
小 A 想给小 B 寄几盒蒜。
R2R^2R2 平面上有五个特殊点$ A,B,C,D,E$，任意两点不重合，任意三点不共线。
小 A 可以任意选择 A,B,C,D,E{A,B,C,D,E}A,B,C,D,E 中不同的三个点 P1,P2,P3P_1,P_2,P_3P1,P2,P3，并记 △P1P2P3△P_1P_2P_3△P1P2P3 的外接圆为 C。小 A 只能在 C 上移动。
记以 ${A,B,C,D,E}∖{P_1,P_2,P_3} $中剩余的两个点 P4,P5P_4,P_5P4,P5 所在的直线为 ℓ。小 B 只能在 ℓ 上移动。
小 A 想最小化两人之间的最短距离，使得寄蒜所支付的邮费最少。形式化地说，你需要求出 minC,ℓminP∈C,Q∈ℓ∣PQ∣min_{C,ℓ}min_{P∈C,Q∈ℓ}|PQ|minC,ℓminP∈C,Q∈ℓ∣PQ∣，其中 ∣PQ∣=(xP−xQ)2+(yP−yQ)2|PQ|=\sqrt{(x_P−x_Q)^2+(y_P−y_Q)^2}∣PQ∣=(xP−xQ)2+(yP−yQ)2为线段 $PQ ...
E4-D
E4-D CYCLES
题目描述
题目描述
在这循环往复的季节里，
对你的倾诉仍未说出口。
「我，任何改变都没有吗？」
给定 n 个点 m 条边的带权有向图 G。G 上的点依次标号 1,2,…,n1,2,…,n1,2,…,n。第 iii 条边$ u_i→v_i$ 的起点为 uiu_iui，终点为 viv_ivi，边权为 wiw_iwi。
对于 G 上的环$ p_1→p_2→⋯→p_k→p_1$，定义环的权值为环上所有边的边权平均值。
请你求出 G 上环的权值的最小值。如果 G 上没有环，则认为答案为 0。
输入
本题测试点包含多组数据。
第一行，一个正整数 T（1≤T≤10）T（1≤T≤10）T（1≤T≤10），表示数据组数。
对于每组数据：
第一行，两个正整数$ n,m（1≤n≤10^3，1≤m≤10^3）$，表示 G 的点数与边数。
接下来 m 行，每行三个正整数 ui,vi,wi（1≤ui≤n，1≤vi≤n，1≤wi≤106，ui≠vi）u_i,v_i,w_i（1≤u_i≤n，1≤v_i≤n，1≤w_i≤10^6，u_i≠v_i）ui,vi,wi（1≤ui≤n，1≤ ...
计算几何
计算几何
三点共线
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 ...
求简单多边形面积
PolygonArea
题目描述
莫卡想请你帮她计算一个包含 nnn 个点的简单多边形面积。
输入
第一行包含一个正整数 nnn，代表点数。
接下来n行，每行两个整数 xi,yix_i,y_ixi,yi，代表点的坐标，点的坐标按照逆时针顺序给出。
3≤n≤1000,0≤∣xi∣,∣yi∣≤1063≤n≤1000,0≤|x_i|,|y_i|≤10^63≤n≤1000,0≤∣xi∣,∣yi∣≤106。
输出
输出一个正整数，代表简单多边形面积的两倍。
输入样例
12345425 2540 4010 2040 0
输出样例
1600
鞋带公式
S=12∣∑i=1nxi∗(yi+1−yi−1)∣=12∣∑i=1nyi∗(xi+1−xi−1)∣S=\frac{1}{2}|\sum_{i=1}^{n}x_i*(y_{i+1}-y_{i-1})|=\frac{1}{2}|\sum_{i=1}^{n}y_i*(x_{i+1}-x_{i-1})|
S=21∣i=1∑nxi∗(yi+1−yi−1)∣=21∣i=1∑nyi∗(xi+1−xi−1)∣
设xix_ixi下标从1到n ...
网络流问题
网络流问题
最大流
Ford-Fulkerson算法
概述
最大流问题中，我们主要关注剩余容量。在获得最后各边的剩余容量之后，只需要拿源点的初始容量减去剩余容量即可得到流量。
我们首先寻找一条能抵达汇点的路径，很容易得到该路径能输送的最大流量取决于这条路径最小容量的边。然后将这条路径加上该流量，更新剩余容量。当某条边剩余流量为0时我们将无法再通过它来输送流量，所以可以考虑将其移除，之后再寻找其他路径，直至无法抵达汇点。我们将这个过程中删除满流的边之后，边权为剩余流量的图称为残量网络。
但是这个过程中无法进行回溯，所以如果我们删除了一条不是最优的边(表示选中了它)那我们将无法放弃选择，从而得不到最优解。Ford−FulkersonFord-FulkersonFord−Fulkerson算法的关键在于，当我们在压入流量的同时在残量网络中添加容量大小与正向流量相等的反向边。
例如：对于节点v1−>v2v1->v2v1−>v2如果v1v1v1流向v2v2v2的容量为6，流量大小为5那么我们添加一条容量(剩余容量)为5的反向边(如果已经存在反向边则更新其容量)。最终不存在路径可 ...
