图论小结（一）包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配

图论小结（一）包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配

[python] 
图论小结（一） 
下面是对暑假集训的图论部分的一些总结和体会。 
包括一些最短路，最小生成树，差分约束，欧拉回路，的经典题和变种题。强连通，双连通，割点割桥的应用。二分匹配，KM，支配集，独立集，还有2-SAT。 
下面就暑假写过的一些题做一个小结。 
[python]
（1）最短路的话一个主要掌握三个算法和两个优化。Dijsktra单源最短路，可以变形他的松弛条件，而产生很多的最短路变种，题型非常灵活。Floyed可求全源最短路。时间复杂度是O（n^3），空间复杂度是O(n^2)，可用于小数据范围的快速求解，更适合于稠密图，另外将更新条件更改还可求传递闭包。还有贪心的floyed倍增。而对于存在负权回路的图来说，bellman-ford可求解该情况下的最短路，如果不存在最短路将会报错。其优化是SPFA。其算法的时间复杂度是O（kE），当边比点大较多倍时，效果不是特别理想。此时dijsktra的heap优化会有更好的效果。由bellman-ford相关的有差分约束系统。其难点在构造出一组相同符号的不等式，然后利用bellman-ford构造进行解的存在性判断。下面是一些相关的题目。 
Heavy Cargo ：这个是求所有边中最小边的最大值。将dijsktra的转移方程更改为dist[j]=max(dist[j],min(dist[k],map[k][j]));其中k是当前的距离最小点，j是松弛遍历的点。 
Frogger ： 这个和上面的相反，是求所有边中最大边的最小值。转移方程改为dist[j]=min(dist[j],min(dist[k]),map[k][j]);注意细节。memset里面的0x7f和常数赋值的0x7f差别很大。常数赋值的数值很小。而memset内部是按照字节进行赋值。是一个很大的值。  
这一道题是一道最短路的变种。实际上是求所有路径中最大边的最小值。 起点是1，终点为2. 
King 差分约束系统: 将所有的不等式全都转化成<=的形式，如<1变为<=0. 注意建模。即构造不等关系。然后将两端点反向存图。接着就上bellman. 
关于最短路还有一些求路径的问题，第k短路，多条最短路问题，还有每条路可重复行走的最短路径问题，二维dijsktra，都等待接下去一个月的陆续补充。 
[python] 
（2）接下去是最小生成树。目前只涉及到很粗浅的部分，不再多说。就几个题。 
Arctic Network，The Bug Sensor Problem 最小生成树求第k大边 。很简单，对所有的边排序即可。 
 Communication Planning for Phobos 最小生成树加计算几何double dis(double x1,double y1,double x2,double y2,double R)   
{    //参数都是弧度表示的   
     x1=pie*x1/180.0;   
     y1=pie*y1/180.0;   
     x2=pie*x2/180.0;   
     y2=pie*y2/180.0;   
     return R*(acos(cos(x1)*cos(x2)*cos(y1-y2)+sin(x1)*sin(x2)));   
}  主要记下一个计算球面点距离的公式即可。 
[python] 
（3）欧拉路径问题。 
欧拉路径问题就写了两篇，但都是博客里访问量较大的两篇，将近一千人。 
第一个是 Play on Words 并查集加欧拉回路： 
该题构图的时候将每个单词拆开，每个单词的第一个字母和最后一个字母记为两个节点，又第一个字母向后一个字母连一条有向边。第一个字母节点的出度++，后一个节点的入度++。 
这道题将图当做无向图，然后用并查集处理连通性的问题。再记录每个点的出度和入度。 然后用欧拉路的定义来求解。存在欧拉回路的条件是：所有点出度==入度。 存在欧拉道路的条件是：有且仅有两个点出度！=入度，且出度和入度之差为1.其余点出度==入度。 
第二个题是关于欧拉途径的拓扑输出问题。 
 John's trip  欧拉回路输出路径：用  g[u][e]=v; g[v][e]=u;的方法将点对应的边记录下来。  
深搜的时候直接输出。 
如果有一个点的度数为奇数，就说明他的入度！=出度。即不存在欧拉回路。 
规律：考虑用欧拉回路解题，一般题目中有每一边（或是点）都只遍历过一次，最后会回到起点，问路径是否存在，若存在，路径输出等问题。 
[python] 
（4）强连通分量。 
如果一个集合内的任意两点两两互达，则该两个点属于一个强连通分量中。强连通分量很重要，也常作为复杂题的预处理，缩点等问题，就是将一个强连通分量等效为一个点来处理。可以通过处理缩点的出度和入度而高效的处理一个图。还可以直接利用强连通分量的性质，判断属于一个强连通分量里的两个点互达性，连通性。 
 The Bottom of a Graph 强连通分量加缩点：题意比较晦涩，大致就是求一个图缩点后出度为0的点的个数 。 
The Busiest Man 强连通分量+缩点+传递闭包 !  
强连通分量+缩点+传递闭包。有n种物品，现给出m种关系，每种关系a,b对应着物品b能够用物品a来换，然后有q个询问(a,b)，问物品a能不能换到物品b。刚开始是判断两个点是否在一个连通分量里，后来想下题目有问单向可达即可，判连通分量范围太小，是错的。这题直接搜索也能过。但是如果传递闭包的话，直接用floyed超时。可以先缩点，再对新图求传递闭包。这是一类关系问题中的单向连通。是一类有代表性的题目。  
[python] 
（5）求一些关于图的性质的题。如求割点和割边。 
SPF ，network ，tarjan算法求割点。具体见博客的代码。 
这类题一般会有删除某个点或某条边将图分为两部分或者不再连通。可以求连通块的个数或者是割点的个数，割边的个数，割点的编号。 
[python]
（6）二分图匹配。 
二分图匹配和2-SAT其实都是下面即将讲到的网络流的一个分支吧。其实这些图问题是共通的吧。“一切问题皆网络流”。这些问题都可以转化为网络流来求解。但是又由于二分图和2-SAT有着自己模型和特点，所以有着更为简便的解法。 
首先二分图最大匹配等价于最小点集覆盖。 
这些题一般都会给一些配对关系，然后求最大可匹配的组数。构图的时候有的需要将点离散开处理T-Shirt Gumbo 二分最大匹配 hoj ，有些需要将点拆分，如两个棋盘覆盖问题。建立点和点自身的匹配关系。 
下面主要介绍下棋盘覆盖的二分图经典模型。 
Don't Get Rooked 二分最大匹配经典题  
可以把一个图拆分成两个图。一个统计行，另一个统计列。如果一行连续，则将该连续块打上一个相同的标号，否则，标号加1，该部分的处理有点麻烦。这两个图的坐标如果有相等的部分，就在此连一条边.也是点拆分的建图方法，自身条件匹配，很经典的题。  
poj 2446 Chessboard 二分图最大匹配经典题  
题意是在一些有洞的棋盘上用一个1x2的方形条将棋盘完全填满。可以对不是洞的每一个点找和他相邻的点，如果他相邻的点也不是洞的话，就画一条边。然后获取标号。实际上就是一个将一个点拆分成两个点的想法。将||可能||，可能匹配的点都连一条！！  www.2cto.com
[python] 
（7）网络流。这是一个大块。关于这个部分的很多总结都要留待以后，在此只做几道模板题的说明。网络题重点是建模。建立图的网络模型。然后模板套之。 
 A Plug for UNIX 最大流 
题意就是给了你m个电器，n个插头，tt个转换器，以及自己增加一个虚拟的源点和汇点。将转换器和插头相连的边置为无穷大。  
其余的边长度都置为1.该模板中n表示图中节点的总数。最后要记得修改。还有一点需要注意的就是转换不是只有样例中给出的'X，可能有无数个，无数种类型。  
在这里借鉴了一种网上map的写法。很简介。下面这个网址给了一张图很详细。一看便知http://www.cnblogs.com/longdouhzt/archive/2011/09/03/2165860.html 
 Power Network 最大流基础 hoj 
题意中给出多个节点和多个发电站与消费站。可以建一个虚拟的源点和虚拟的汇点，将所有的发电站和源点连一条边，将所有的消费占和汇点连一条边。  
然后利用网络流建图即可。下面是SAP算法。 
也是给定一些匹配关系求最值问题的模型。