今天是丁明朔老师的讲授~
图论
图是种抽象结构，这种抽象结构可以表示点与点之间的关系。
最短路：
Dijkstra（堆优化）
SPFA
Floyd
最小生成树：
Kruscal
连通性：
BFS / DFS
Tarian（强连通分量）
其他：
拓扑排序
LCA
啥都不说先看下经典例题：
-_-||暂时不考虑特殊的性取向），如果一对男女互有好感，那么你就可以把这一对撮合在一起，现在让我们无视掉所有的单相思（好忧伤的感觉
），你拥有的大概就是下面这样一张关系图，每一条连线都表示互有好感。
)重新找个妹子(注意这个步骤和上面是一样的，这是一个递归的过程)
此时发现2号男生还能找到3号女生，那么之前的问题迎刃而解了，回溯回去
所以第三步最后的结果就是：
===============================================================
四： 接下来是4号男生，很遗憾，按照第三步的节奏我们没法给4号男生腾出来一个妹子，我们实在是无能为力了……香吉士同学走好。
===============================================================
这就是匈牙利算法的流程，其中找妹子是个递归的过程，最最关键的字就是“ 腾 ”字；
其原则大概是：有机会上，没机会创造机会也要上！
代码也很好懂滴：
int vis[],girl[]; //girl[i]表示第i个妹子喜欢哪个男的,vis[i]表示当前这一轮妹子有没有被考虑过
int f[][]; //f[i][j]表示i和j是否有好感 bool work(int x)
{
for(int i=;i<n;i++) //寻找每个妹子
{
if(!vis[i]&&f[x][i]) //如果这个妹子没被别的男的考虑过并且他俩又好感,可以尝试匹配一下
{
vis[i]=; //这个妹子在这一轮我已经考虑过了,其他男的别想了
if(!girl[i]||work(girl[i])) //如果妹子没有喜欢的人或者妹子喜欢的那个人可以找到另一个妹子的话
{
girl[i]=x; //那就将这个妹子安排给 x
return ;
}
}
}
return ; //否则的话就安排不上了,没有哪个男的会白白让出自己的妹子的QAQ
}
裸的匈牙利算法。
只不过需要注意如果我们当前有一个题没有找到锦囊，那么后面就不用再找了，直接 break 跳出就好了。
差分约束
差分约束系统，是求解关于一组变数的特殊不等式组之方法。
如果一个系统由
个变量和
个约束条件组成，其中每个约束条件形如
，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
一.树形结合
然后继续回到单个不等式上来，观察 x [ i ] – x [ j ] <= a [ k ] ， 将这个不等式稍稍变形，将 x [ j ] 移到不等式右边，则有 x [ i ] <= x [ j ] + a [ k ] ，然后我们令 a [ k ] = w( j, i )，再将不等式中的 i 和 j 变量替换掉，i = v， j = u，将 x 数组的名字改成 d（以上都是等价变换，不会改变原有不等式的性质），则原先的不等式变成了以下形式：d [ u ] + w( u, v ) >= d [ v ]。
这时候联想到SPFA中的一个松弛操作：
if(d[u] + w(u, v) < d[v])
{d[v] = d[u] + w(u, v);}
对比上面的不等式，两个不等式的不等号正好相反，但是再仔细一想，其实它们的逻辑是一致的，因为SPFA的松弛操作是在满足小于的情况下进行松弛，力求达到 d [ u ] + w( u, v ) >= d [ v ]，而我们之前令 a [ k ] = w( j, i )，所以我们可以将每个不等式转化成图上的有向边：对于每个不等式 x [ i ] – x [ j ] <= a [ k ]，对结点 j 和 i 建立一条 j -> i的有向边，边权为 a [ k ]，求 x [ n-1 ] – x [ 0 ] 的最大值就是求 0 到n-1的最短路。
二.三角不等式
如果还没有完全理解，我们可以先来看一个简单的情况，如下三个不等式：
B – A <= c （1）
C – B <= a （2）
C – A <= b （3）
我们想要知道C – A的最大值，通过(1) + (2)，可以得到 C – A <= a + c，所以这个问题其实就是求 min { b, a+c }。将上面的三个不等式按照数形结合中提到的方式建图：
发现 b 和 a+c 都是 A -> C 的路径，我们实际上再求最短路！
这就是著名的三角形不等式，将三个不等式推广到m个，变量推广到n个，就变成了n个点m条边的最短路问题了。
三. 最大值 => 最小值
然后，我们将问题进行一个简单的转化，将原先的”<=”变成”>=”，转化后的不等式如下：
B – A >= c (1)
C – B >= a (2)
C – A >= b (3)
然后求C – A的最小值，类比之前的方法，需要求的其实是 max { b, c+a }，于是对应的是图三-2-1从A到C的最长路。同样可以推广到n个变量m个不等式的情况。
所以我们求最小值就跑最长路，求最大值就跑最短路！
