图论（入门版）
目录
1 向、权
2 最小生成树
2.1 Prim算法
2.2 Kruskal算法
3 最大流问题
3.1 Naive算法
3.2 Ford—Fulkerson算法
3.3 Edmonds—Karp算法
3.4 Dinic算法
4 最小割问题
5 二部图
5.1 判断是否是二部图的方法
5.2 匈牙利算法（最小匹配问题）
5.3 最大匹配问题
5.4 婚配问题
1 向、权
向：一点和另一点之间有单向和双向两种情况
如果A与B间是双箭头或一条无向线相连，代表无向，即可以从A走向B，也可以从B走向A
权：从一点到另一点的代价
如果任何点之间的代价相同，代表无权，反之，则有权
所以，可以分为四类图：无向无权图、无向有权图、有向无权图、有向有权图
对于无权图，可以运用队列+搜索思想，把起点压入队列，然后把起点弹出队列，同时找到能直接到达的结点并压入队列，循环多次直到队列为空时结束循环，可以把所有结点都遍历一遍。
对于有权图，运用优先队列+搜索思想，和上面操作等同，但要同时记录权。
下图是有向无权图：
2 最小生成树
图和树最大的区别是树一定不能有回路，图没有要求，所以说树是特殊的图
2.1 Prim算法
思路：找已搜索过的点和未搜索过的点之间的最小通路
1：随机找一个起点
2：搜索出所有的和起点连通的路
3：找出代价最小的一条路并连接，这个点和起点在一棵树上
4：按照前面的步骤进行循环，直到所有的点都在一棵树上
判断是否在一棵树上用并查集：
#include <iostream>
using namespace std;
int n,m,p;
const int N=5e3+10;
int fa[N];
int init()
{
for(int i=0;i<N;i++)
{
fa[i]=i;
}
}
int find(int x)
{
int t=x;
while(t!=fa[t])
{
t=fa[t];
}
while(x!=fa[x])
{
int temp=fa[x];
fa[x]=t;
x=temp;
}
}
void merge(int a,int b)
{
a=find(a);
b=find(b);
if(a!=b)
{
fa[b]=a;//结合到一起，也可以是fa[a]=b;
}
}
int main()
{
cin>>n>>m>>p;
init();//初始化父节点；
int u,v;
while(m--)
{
cin>>u>>v;
merge(u,v);
}
while(p--)
{
cin>>u>>v;
u=find(u);
v=find(v);
puts(u==v?"Yes":"No");
}
}2.2 Kruskal算法
直接把所有路的代价按照从小到大排序，并按此顺序连接结点，注意在连接结点前要判断两结点是否已经在一棵树内，若在一棵树内，则直接跳过。
3 最大流问题
对于一张建设好的网络(流网络)(各边上的数值表示流的容量限制,箭头表示流动方向,该网络的建设好后不允许更改):
考察其最大流是指从源点提供流(假设提供能力总是充足的)
那么管道中的流从s->t的过程中所能达到的最大值是多少?
3.1 Naive算法
这种算法不是好的算法，对于一些情况来说不能算出最好结果，但这种算法为后面的好的算法提供思路。
找简单路（不绕圈的路，即所有路过的结点不重复，随便找一条符合条件的就行）和简单路中的最小权重，所以这段水流=这条最小路的权重，然后把消耗值减掉，再把权重为0的边去掉，如果起点和终点已经不在一棵树内，则停止循环。这里计算出的“最大流”成为阻塞流
3.2 Ford—Fulkerson算法
这种算法比Naive算法多出的一条是，消耗值要反向加回到图中，而不是简单的减去就结束了
3.3 Edmonds—Karp算法
这种算法比Ford—Fulkerson算法多出的一条是，找简单路时要找最短路径
3.4 Dinic算法
思路：
1：画一张阶梯图（要求路只能连接不同层之间的结点），并计算阻塞流（Naive算法）
2：把Naive算法中算出的所有路的消耗值反向加回到原图中
3：根据2得到的图画阶梯图，然后进入步骤1（来回循环），当找不到阻塞流时结束循环
4 最小割问题
选取某些路并割去，使得没有一条路能从起点走到终点，割去路的加和最小值=最小割
结论：最大流=最小割
5 二部图
5.1 判断是否是二部图的方法
1：随意找一个点染成红色
2：把红色结点的邻接结点染成蓝色
3：把蓝色结点的邻接结点染成红色
4：如此往复，如果此过程没有出现矛盾，则是二部图
5.2 匈牙利算法（最小匹配问题）
这里假设有两个集合U和V，每个集合有三个元素u1、u2、u3、v1、v2、v3。
画一张表格：
| u1 | u2 | u3 | |
| v1 | 8 | 9 | 10 |
| v2 | 7 | 3 | 9 |
| v3 | 5 | 6 | 2 |
减去每行最小值和每列最小值：
| u1 | u2 | u3 | |
| v1 | 0（-8） | 1（-8） | 2（-8） |
| v2 | 4（-3） | 0（-3） | 6（-3） |
| v3 | 3（-2） | 4（-2） | 0（-2） |
使得每一行每一列都出现至少一个0。然后对0相应的元素的原始值进行处理即可。
图形思路：
色块和白块分别有4个，如何才能使匹配量最多？
M1可以和NA直接匹配
M2发现此时NA已经被匹配了，把M1和NA强行分开，M1此时就找NC匹配
M3找NB匹配，但这样的话M4就不能匹配了，所以M3只能和ND匹配，这样M4也能匹配
5.3 最大匹配问题
把原始数据变成相反数，变成最小匹配问题即可。
