《图论算法总结及图论建模ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论算法总结及图论建模ppt课件.ppt（121页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论算法总结图的基本概念图的基本概念二元组二元组 G(V,E) 称为图称为图(graph)。 V为结点为结点(node)或顶点或顶点(vertex)集。集。 E为图中结点之间的边的集合。为图中结点之间的边的集合。点，用数字点，用数字0n-1表示表示点对点对 (u,v) 称为边称为边(edge)或称弧或称弧(arc)对于边对于边 (u,v)E-u和和v邻接邻接(adjacent)-e和和u、v关联关联(incident)子图子图(subgraph): 边的子集和相关联的点集边的子集和相关联的点集图的基本概念有向图：边都是单向有向图：边都是单向(unidirectional)的的, 因此边因此边(
2、u,v)是有序数对是有序数对. 有时用弧有时用弧(arc)专指有向边专指有向边带权图：可以给边加权带权图：可以给边加权(weight), 成为带权图成为带权图, 或加权图或加权图(weighted graph). 权通常代表费用、距离等权通常代表费用、距离等, 可以是正数可以是正数, 也可以是负数也可以是负数稠密性：边和稠密性：边和V(V-1)/2相比非常少的称为稀疏图相比非常少的称为稀疏图(sparse graph), 它的补图为稠密图它的补图为稠密图(dense graph)路径和圈一条路径一条路径(path)是一个结点序列是一个结点序列, 路上的相邻结点在图上是邻接的路上的相邻结点在图上
3、是邻接的如果结点和边都不重复出现如果结点和边都不重复出现, 则称为简单路径则称为简单路径(simple path). 如果如果除了起点和终点相同外没有重复顶点和边除了起点和终点相同外没有重复顶点和边, 称为圈称为圈(cycle). 不相交路不相交路(disjoint path)表示没有除了起点和终点没有公共点的路表示没有除了起点和终点没有公共点的路. 更严格地更严格地-任意点都不相同的叫严格不相交路任意点都不相同的叫严格不相交路(vertex-disjoint path)-同理定义边不相交同理定义边不相交(edge-disjoint path)路路注意注意: 汉语中圈和环经常混用汉语中圈和环经
4、常混用(包括一些固定术语包括一些固定术语). 由于一般不讨由于一般不讨论自环论自环(self-loop), 所以以后假设二者等价而不会引起混淆所以以后假设二者等价而不会引起混淆连通性如果任意两点都有路径如果任意两点都有路径, 则称图是连通则称图是连通(connected)的的, 否则称图是否则称图是非连通的非连通的. 非连通图有多个连通分量非连通图有多个连通分量(connected component, cc), 每个连通分每个连通分量是一个极大连通子图量是一个极大连通子图(maximal connected subgraph)完全图和补图完全图完全图:N个顶点的图，有个顶点的图，有N(N-1
5、)/2个节点个节点对于对于(u,v), 若邻接则改为非邻接若邻接则改为非邻接, 若非邻接则改为邻接若非邻接则改为邻接, 得到的图得到的图为原图的补图为原图的补图完全图完全图=原图原图补图补图团：完全子图团：完全子图生成树树：树：N个点，个点，N-1条边的连通图（无环连通图）条边的连通图（无环连通图）生成树生成树: 包含某图包含某图G所有点的树所有点的树一个图一个图G是树当且仅当以下任意一个条件成立是树当且仅当以下任意一个条件成立G有有V-1条边条边, 无圈无圈G有有V-1条边条边, 连通连通任意两点只有唯一的简单路径任意两点只有唯一的简单路径G连通连通, 但任意删除一条边后不连通但任意删除一条
6、边后不连通图例图的表示方法介绍两种图的表示方法：邻接矩阵与邻接表介绍两种图的表示方法：邻接矩阵与邻接表V*V的二维数组的二维数组A，Aij=0,若若(i,j)不相连，不相连，Aij=1,若若(i,j)相连相连图图1图图1的邻接矩阵表示的邻接矩阵表示邻接矩阵无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的优点：查找优点：查找/删除某条边是删除某条边是O(1)的的缺点缺点遍历某一点的邻居是遍历某一点的邻居是O(V)的的空间复杂度很大，空间复杂度很大，O(V*V)每个结点的邻居形成一个链表每个结点的邻居形成一个链表邻接表图图2图图2的邻接表表示的邻接表表示优点优点快速遍历某点所有邻居快速遍历某点所有
7、邻居占用存储空间小，是占用存储空间小，是O（边数）的，在稀疏图上的效率远胜（边数）的，在稀疏图上的效率远胜邻接表邻接表缺点：查找缺点：查找/删除边不是常数时间删除边不是常数时间邻接表图的遍历算法给定图给定图G和一个源点和一个源点s, 宽度优先遍历按照从近到远的顺序考虑各条宽度优先遍历按照从近到远的顺序考虑各条边边. 算法求出从算法求出从s到各点的距离到各点的距离宽度优先的过程对结点着色宽度优先的过程对结点着色. 白色白色: 没有考虑过的点没有考虑过的点黑色黑色: 已经完全考虑过的点已经完全考虑过的点灰色灰色: 发现过发现过, 但没有处理过但没有处理过, 是遍历边界是遍历边界依次处理每个灰色结点
8、依次处理每个灰色结点u, 对于邻接边对于邻接边(u, v), 把把v着成灰色并加入树着成灰色并加入树中中, 在树中在树中u是是v的父亲的父亲(parent)或称前驱或称前驱(predecessor). 距离距离dv = du + 1整棵树的根为整棵树的根为s宽度优先遍历(BFS)题目大意：题目大意： 给出给出N*M个格子，给出个格子，给出K个已经被淹没的格子，其他格子都是个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为干的，求最大的湖的面积（一个格子的面积视为1），如果两个），如果两个湿的格子四联通（上下左右），则视为这两个格子同属于一个湖湿的格子四联通（上下左右），
9、则视为这两个格子同属于一个湖输入格式：输入格式： 第一行第一行N，M，K 接下来接下来K个格子的坐标个格子的坐标Avoid The Lakes （NOI题库2405）Input3 4 5 3 2 2 2 3 1 2 3 1 1 Output4样例解释样例解释#.#.#.新发现的结点先扩展新发现的结点先扩展得到的可能不是一棵树而是森林得到的可能不是一棵树而是森林, 即深度优先森林即深度优先森林(Depth-first forest)特别之处特别之处: 引入时间戳引入时间戳(timestamp)发现时间发现时间dv: 变灰的时间变灰的时间结束时间结束时间fv: 变黑的时间变黑的时间1=dv fv
10、= 2|V|深度优先遍历(DFS)初始化初始化: time为为0, 所有点为白色所有点为白色, dfs森林为空森林为空对每个白色点对每个白色点u执行一次执行一次DFS-VISIT(u)时间复杂度为时间复杂度为O(n+m)深度优先遍历(DFS)括号结构性质括号结构性质对于任意结点对对于任意结点对(u, v), 考虑区间考虑区间du, fu和和dv, fv, 以下三个性质恰有一个成立以下三个性质恰有一个成立:完全分离完全分离u的区间完全包含在的区间完全包含在v的区间内的区间内, 则在则在dfs树上树上u是是v的后代的后代v的区间完全包含在的区间完全包含在u的区间内的区间内, 则在则在dfs树上树上
11、v是是u的后代的后代DFS树的性质定理定理(嵌套区间定理嵌套区间定理):在在DFS森林中森林中v是是u的后代当且仅当的后代当且仅当dudvfvfu, 即区间包含关系即区间包含关系. 由区间性质立即得到由区间性质立即得到.DFS树的性质一条边一条边(u, v)可以按如下规则分类可以按如下规则分类树边树边(Tree Edges, T): v通过边通过边(u, v)发现发现后向边后向边(Back Edges, B): u是是v的后代的后代前向边前向边(Forward Edges, F): v是是u的后代的后代交叉边交叉边(Cross Edges, C): 其他边，可以连接同一个其他边，可以连接同一个
12、DFS树中没树中没有后代关系的两个结点有后代关系的两个结点, 也可以连接不同也可以连接不同DFS树中的结点树中的结点判断后代关系可以借助定理判断后代关系可以借助定理1边的分类当当(u, v)第一次被遍历第一次被遍历, 考虑考虑v的颜色的颜色白色白色, (u,v)为为T边边灰色灰色, (u,v)为为B边边 (只有它的祖先是灰色只有它的祖先是灰色)黑色黑色: (u,v)为为F边或边或C边边. 此时需要进一步判断此时需要进一步判断dudv: C边边 (v早就被发现了早就被发现了, 为另一为另一DFS树中树中)时间复杂度时间复杂度: O(n+m)定理定理: 无向图只有无向图只有T边和边和B边边 (易证
13、易证)边分类算法if (dv = -1) dfs(v); /树边树边, 递归遍历递归遍历else if (fv = -1) show(“B”); /后向边后向边else if (dv du) show(“F”); / 前向边前向边else show(“C”); / 交叉边交叉边d和和f数组的初值均为数组的初值均为-1, 方便了判断方便了判断实现细节实现细节DAG:有向无环图有向无环图拓扑顺序：拓扑顺序：拓扑排序算法对图对图G使用使用DFS算法算法, 每次把一个结点变黑的同时加到链表首部每次把一个结点变黑的同时加到链表首部AN EXAMPLE定理定理1: 有向图是有向图是DAG当且仅当没有返祖边
14、当且仅当没有返祖边如果有返祖边如果有返祖边, 有环有环(易证易证)如果有环如果有环c, 考虑其中第一个被发现的结点考虑其中第一个被发现的结点v, 环中环中v的上一个结点为的上一个结点为u, 则则沿环的路径沿环的路径vu是白色路径是白色路径, u是是v的后代的后代, 因此因此(u, v)是返祖边是返祖边定理定理2: 该算法正确的得到了一个拓扑顺序的逆序该算法正确的得到了一个拓扑顺序的逆序拓扑排序算法一、有向图一、有向图: SCC划分的划分的Kosaraju算法算法(有兴趣的同学自己看吧有兴趣的同学自己看吧)二、有向图二、有向图: SCC划分的划分的Tarjan算法算法三、无向图三、无向图: 割顶
15、和桥的判定割顶和桥的判定图的连通性算法有向图中有向图中, u可达可达v不一定意味着不一定意味着v可达可达u. 相互可达则属于同一个强连通分量相互可达则属于同一个强连通分量 (Strongly Connected Component, SCC)有向图和它的转置的强连通分量相同有向图和它的转置的强连通分量相同所有所有SCC构成一个构成一个DAGSCC的概念Tarjan算法是基于对图深度优先搜索的算法算法是基于对图深度优先搜索的算法每个强连通分量为搜索树中的一棵子树每个强连通分量为搜索树中的一棵子树搜索时，把当前搜索树中未处理的节点加入一个堆栈搜索时，把当前搜索树中未处理的节点加入一个堆栈回溯时可以
16、判断栈顶到栈中的节点是否为一个强连通分量。回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。tarjan算法(参考byvoid博客)定义：定义：DFN(u)为节点为节点u搜索的次序编号搜索的次序编号(时间戳时间戳)Low(u)为为u或或u的子树能够追溯到的最早的栈中节点的次序号的子树能够追溯到的最早的栈中节点的次序号当当DFN(u)=Low(u)时，以时，以u为根的搜索子树上所有节点是一个强为根的搜索子树上所有节点是一个强连通分量。连通分量。dfn与low函数算法伪代码tarjan(u) DFNu=Lowu=+Index / 为节点为节点u设定次序编号和设定次序编号和Low初值初值 Stac
17、k.push(u) / 将节点将节点u压入栈中压入栈中 for each (u, v) in E / 枚举每一条边枚举每一条边 if (v is not visted) / 如果节点如果节点v未被访问过未被访问过 tarjan(v) / 继续向下找继续向下找 Lowu = min(Lowu, Lowv) else if (v in S) / 如果节点如果节点v还在栈内还在栈内 Lowu = min(Lowu, DFNv) if (DFNu = Lowu) / 如果节点如果节点u是强连通分量的根是强连通分量的根 repeat v = S.pop / 将将v退栈，为该强连通分量中一个顶点退栈，为该
18、强连通分量中一个顶点 print v until (u= v)算法演示算法演示算法演示算法演示完整代码void tarjan(int i) int j; DFNi=LOWi=+Dindex; instacki=true; Stap+Stop=i; for (edge *e=Vi;e;e=e-next) j=e-t; if (!DFNj) tarjan(j); if (LOWjLOWi) LOWi=LOWj; else if (instackj & DFNjLOWi) LOWi=DFNj; if (DFNi=LOWi) Bcnt+; do j=StapStop-; instackj=false;
19、 Belongj=Bcnt; while (j!=i); void solve() int i; Stop=Bcnt=Dindex=0; memset(DFN,0,sizeof(DFN); for (i=1;i=N;i+) if (!DFNi) tarjan(i);N头奶牛头奶牛(N10000)M对关系（对关系（a , b），表示），表示a认为认为b是受欢迎的是受欢迎的关系具有传递性，即若关系具有传递性，即若(a,b),(b,c)(a,c)询问有多少头奶牛是被其他所有奶牛认为是受欢迎的询问有多少头奶牛是被其他所有奶牛认为是受欢迎的Popular Cows ( POJ2186 )求出所有的强连通
20、分量求出所有的强连通分量每个强连通分量缩成一点，则形成一个有向无环图每个强连通分量缩成一点，则形成一个有向无环图DAG。DAG上面如果有唯一的出度为上面如果有唯一的出度为0的点，则该点能被所有的点可达。的点，则该点能被所有的点可达。 那么该点所代表的连通分量上的所有的原图中的点，都能被原图那么该点所代表的连通分量上的所有的原图中的点，都能被原图中中 的所有点可达的所有点可达 ，则该连通分量的点数就是答案。，则该连通分量的点数就是答案。DAG上面如果有不止一个出度为上面如果有不止一个出度为0的点，则这些点互相不可达，的点，则这些点互相不可达，原问题无解，答案为原问题无解，答案为0；Popular
21、 Cows ( POJ2186 )procedure tarjan(u:longint);var p:node; v:longint;begin fu:=false;inc(top);stacktop:=u; instacku:=true;p:=headu; inc(time);dfnu:=time;lowu:=time; while p.keyu do begin v:=p.key; if fv then begin tarjan(v);lowu:=min(lowu,lowv); end else begin if instackv then lowu:=min(lowu,dfnv); en
22、d; p:=p.next; end; if lowu=dfnu then begin inc(s); while stacktopu do begin instackstacktop:=false; jdstacktop:=s; top:=top-1; end; instackstacktop:=false; jdstacktop:=s; top:=top-1; end;end;begin read(n); for i:=1 to n do begin new(headi); headi.key:=i; headi.next:=nil; end; read(m); s:=0; for i:=1
23、 to m do begin read(edgexi,edgeyi); new(p); p.key:=edgeyi; p.next:=headedgexi; headedgexi:=p; end; fillchar(f,sizeof(f),true); fillchar(instack,sizeof(instack),false); top:=0;time:=0; for i:=1 to n do if fi then tarjan(i); fillchar(s1,sizeof(s1),0); for i:=1 to m do begin if jdedgexijdedgeyi then in
24、c(s1jdedgexi); end; s2:=0; s3:=0; for i:=1 to s do if s1i0 then inc(s2) else begin for j:=1 to n do if jdj=i then inc(s3); end; if s2+1=s then writeln(s3) else writeln(0);end.对于无向连通图对于无向连通图G割顶是去掉以后让图不连通的点割顶是去掉以后让图不连通的点桥是去掉以后让图不连通的边桥是去掉以后让图不连通的边割顶与桥lowu为为u及其的后代所能追溯到的最早及其的后代所能追溯到的最早(最先被发现最先被发现)祖先点祖先点v
25、的的dfnv值值类似有向图的计算方式类似有向图的计算方式, 注意无向图只有注意无向图只有T和和B边边lowu = dfnu = time+;for (u的不等于的不等于u的邻居的邻居v) / 不考虑自环不考虑自环 if (prev = -1) / 白色点白色点 dfs-visit(v); if (lowu lowv) lowu = lowv; else if (lowu dfnv) lowu = dfnv; 无向图的LOW函数在一棵在一棵DFS树中树中根根root是割顶当且仅当它至少有两个儿子是割顶当且仅当它至少有两个儿子其他点其他点v是割顶当且仅当它有一个儿子是割顶当且仅当它有一个儿子u,
26、从从u或者或者u的后代出发没有的后代出发没有指向指向v祖先祖先(不含不含v)的的B边边, 则删除则删除v以后以后u和和v的父亲不连通的父亲不连通, 故为割顶故为割顶割顶判定算法割顶判定算法:对于对于DFS树根树根, 判断度数是否大于判断度数是否大于1对于其他点对于其他点u, 如果不是根的直接儿子如果不是根的直接儿子, 且且lowu = dfnPu, 则它的则它的父亲父亲v=Pu是割点是割点割顶的判定Network (POJ 1144) void dfs(int u,int dep) dfnu=lowu=dep; for (int i=0; i=dfnu) cutu=true; /由后继节点搜不
27、到比该点更早的点，则该点是割点由后继节点搜不到比该点更早的点，则该点是割点 else lowu=min(lowu,dfnv); 题目大意：给定题目大意：给定一个无向图，求一个无向图，求有多少点是割点有多少点是割点边边(u,v)为桥当且仅当它不在任何一个简单回路中为桥当且仅当它不在任何一个简单回路中发现发现T边边(u,v)时若发现时若发现v和它的后代不存在一条连接和它的后代不存在一条连接u或其祖先的或其祖先的B边边, 则删除则删除(u,v)后后u和和v不连通不连通, 因此因此(u,v)为桥为桥桥的判定算法桥的判定算法: 发现发现T边边(u, v)时若时若LOWvdu(注意不能取等号注意不能取等号
28、), 则则(u,v)为桥为桥桥的判定Byteotia有有n个镇。有的镇被双向的道路连接。每一对镇间最多只个镇。有的镇被双向的道路连接。每一对镇间最多只有一条直接连接的道路。任意两个镇连通。有一条直接连接的道路。任意两个镇连通。每个镇刚好有一个市民。他们为孤独所困。每个居民都想看看其每个镇刚好有一个市民。他们为孤独所困。每个居民都想看看其他所有居民（去他所在的地方），而且刚好做一次。所以刚好发他所有居民（去他所在的地方），而且刚好做一次。所以刚好发生了生了n*(n-1)次访问。不幸的是，一些程序员正在罢工，为了使软次访问。不幸的是，一些程序员正在罢工，为了使软件的销售量提高。作为抗议活动的一部分
29、，程序员想把件的销售量提高。作为抗议活动的一部分，程序员想把Byteotia的一条道路关闭，阻止通过这条道路。他们正在辩论选择哪一条的一条道路关闭，阻止通过这条道路。他们正在辩论选择哪一条道路会使得后果最严重。（后果最严重即删去这条道路后访问次道路会使得后果最严重。（后果最严重即删去这条道路后访问次数最少）数最少）例题例题如图，若删去如图，若删去D,E之间之间的边，则会减少的边，则会减少16次次访问，若删去访问，若删去G,H之间之间的，会减少的，会减少7次访问。次访问。若删除其它边，则不若删除其它边，则不会减少访问次数。会减少访问次数。ACBGDFEH应该删除哪些边？应该删除哪些边？很显然，只
30、有删除桥才会减少访问次数，删去其它的边，很显然，只有删除桥才会减少访问次数，删去其它的边，图依然保持连通。图依然保持连通。因此，首先应该求出所有的桥。因此，首先应该求出所有的桥。例题然后我们分别考虑每个桥的情况，删去这条边，会导致然后我们分别考虑每个桥的情况，删去这条边，会导致把图分成把图分成2个部分，而这两个部分是不连通的。考虑损个部分，而这两个部分是不连通的。考虑损失掉的访问，其实就是跨越这两个部分的访问，即失掉的访问，其实就是跨越这两个部分的访问，即|S1|*|S2|次访问，次访问，|S1|,|S2|是两个部分的大小。是两个部分的大小。由此，大致的算法就形成了，枚举每一条边，然后计算由此
31、，大致的算法就形成了，枚举每一条边，然后计算损失的访问，最后输出答案即可。损失的访问，最后输出答案即可。例题procedure tarjan(u:longint);var p:node; v:longint;begin fu:=false;inc(time); lowu:=time;dfnu:=time;p:=headu; while p.keyu do begin v:=p.key; if fv then begin fav:=u; tarjan(v); lowu:=min(lowu,lowv); if lowvdfnu then begin inc(s); x1s:=u; y1s:=v;
32、end; end else if fauv then lowu:=min(lowu,dfnv); p:=p.next; end;end;function dfs(u:longint):longint;begin fu:=false;p:=headu; while p.keyu do begin v:=p.key; if fv then begin treeu:=treeu+dfs(v); fav:=u; end ; p:=p.next; end; inc(treeu); exit(treeu);end;function count(x:longint):longint;begin while
33、fax0 do x:=fax; count:=treex;end;begin read(n); for i:=1 to n do begin new(headi); headi.key:=i;headi.next:=nil; end; read(m); for i:=1 to m do begin read(x,y); new(p); p.next:=headx; p.key:=y; headx:=p;new(p); p.next:=heady; p.key:=x; heady:=p; end; fillchar(f,sizeof(f),true); s:=0; for i:=1 to n d
34、o begin if fi then begin time:=0; tarjan(i); end; end; fillchar(f,sizeof(f),true); fillchar(tree,sizeof(tree),0); fillchar(fa,sizeof(fa),0); for i:=1 to n do begin if fi then temp:=dfs(i); end; max:=0; for i:=1 to s do begin c1:=treex1i; c2:=treey1i; if c1c2 then c3:=(count(c1)-treey1i)*treey1i else
35、 c3:=(count(c2)-treex1i)*treex1i; if c3max then begin max:=c3; x2:=x1i; y2:=y1i; end; end; writeln(max, ,x2, ,y2);end.给定一张连通图给定一张连通图G（V , E）(V=5,000，E=10,000)询问至少要添加多少条边，使得，任意两点间至少有询问至少要添加多少条边，使得，任意两点间至少有2条路径可条路径可达？达？Redundant Paths (POJ 3177)Redundant Paths (POJ 3177) if dfnu=lowu then begin inc(s)
36、; while stacktopu do begin instackstacktop:=false; hashstacktop:=s; stacktop:=0;dec(top); end; instackstacktop:=false; hashstacktop:=s; stacktop:=0;dec(top); end;end;fillchar(map,sizeof(map),true); fillchar(s2,sizeof(s2),0); for i:=1 to m do begin if (hashxihashyi)and (maphashxi,hashyi) then begin m
37、aphashxi,hashyi:=false; maphashyi,hashxi:=false; inc(s2hashxi); inc(s2hashyi); end; end; s1:=0; for i:=1 to s do if s2i=1 then inc(s1); writeln(s1+1) div 2);end.图的最短路问题SSSP的 Spfa算法SSSP的 Dijkstra算法差分约束系统Floyd-warshall算法给定带权图和一个起点给定带权图和一个起点s, 求求s到所有点的最短路到所有点的最短路(边权和最小的路边权和最小的路径径)最短路有环吗最短路有环吗正环正环: : 何必
38、呢何必呢, , 删除环则得到更短路删除环则得到更短路负环负环: : 无最短路无最短路, , 因为可以沿负环兜圈子因为可以沿负环兜圈子单源最短路问题(Single Source Shortest Path)最优性原理最优性原理: 若最短路若最短路uv经过中间结点经过中间结点w, 则则uw和和wv的路的路径分别是径分别是u到到w和和w到到v的最短路的最短路意义意义: 贪心、动态规划贪心、动态规划最优性原理最短路的表示最短路的表示s到所有点的最短路不需要分别表示到所有点的最短路不需要分别表示最短路树最短路树: 到每个点都沿着树上的唯一路径走到每个点都沿着树上的唯一路径走实际代码实际代码: 记录每个点
39、的父亲记录每个点的父亲predu即可即可输出最短路输出最短路: 从终点沿着从终点沿着predu递推回起点递推回起点最短路的表示松弛（松弛（RELAX）操作）操作一条边一条边(u,v)被称为紧的被称为紧的(tense), 如果如果dist(u)+w(u,v)3-4-5。注意点。注意点2不能在答案路径不能在答案路径中，因为点中，因为点2连了一条边到点连了一条边到点6，而点，而点6不与终点不与终点5连通。连通。大致思路：大致思路：因为路径上的所有点的出边所指向的点都直接或间接与终点连通，因为路径上的所有点的出边所指向的点都直接或间接与终点连通，所以我们不妨把所有的边反向，然后求所以我们不妨把所有的边
40、反向，然后求t到到s的最短路径的最短路径大致证明：大致证明：先将所有边按照读入顺序标号先将所有边按照读入顺序标号所有满足条件所有满足条件1的从的从s到到t路径，在边都反向的情况下，对应一条路径，在边都反向的情况下，对应一条t到到s的路径，并且满足一一对应（因为路径上边的标号都相同）的路径，并且满足一一对应（因为路径上边的标号都相同）Tips：这里的最短路可以：这里的最短路可以BFS求得（因为路径长度都是求得（因为路径长度都是1）NOIP2014Day2T2寻找道路begin/主程序主程序 read(n,m1); for i:=1 to n do begin new(headi);headi:=
41、nil;new(head1i);head1i:=nil; end; for i:=1 to m1 do read(xi,yi); read(a,b); sort(1,m1); m:=0;fillchar(f,sizeof(f),true);x1:=0;y1:=0; fillchar(s,sizeof(s),0); for i:=1 to m1 do begin if xi=yi then fxi:=false else begin if (xi=x1) and (yi=y1) then continue; inc(sxi); inc(m); x1:=xi;y1:=yi; new(p); p.k
42、ey:=y1;p.next:=headx1;headx1:=p; new(p); p.key:=x1; p.next:=head1y1;head1y1:=p; end; end;procedure dfs1(u:longint);/子程序子程序var p:node; v:longint;begin fu:=false; p:=head1u; while pnil do begin v:=p.key; if fv then begin inc(s1v); fv:=false; dfs1(v); end else inc(s1v); p:=p.next; end;end; fillchar(s1,
43、sizeof(s1),0); fillchar(f,sizeof(f),true); dfs1(b);fillchar(al,sizeof(al),true); for i:=1 to n do begin if i=b then continue; if sis1i then ali:=false; end; find:=false; head2:=0; tail:=1; fillchar(q,sizeof(q),0); q1.key:=a; q1.dist:=0; fillchar(f,sizeof(f),true); fa:=false;while head2tail do begin
44、inc(head2);u:=qhead2.key; p:=headu; while pnil do begin v:=p.key; if (fv) and (alv) then begin fv:=false;inc(tail); qtail.key:=v;qtail.dist:=qhead2.dist+1; if v=b then begin writeln(qtail.dist); find:=true; break; end; end; p:=p.next; end; if find then break; if find=false then writeln(-1);end.线性规划线
45、性规划(linear programming, LP): 给给m*n矩阵矩阵A、m维向维向量量b和和n维向量维向量c, 求出求出x为向量使得为向量使得Ax=b, 且且sumcixi最小最小可行性问题可行性问题(feasibility problem): 只需要任意找出一组满足只需要任意找出一组满足Ax=b的解向量的解向量x差分约束系统差分约束系统(system of difference constraints): A的每行恰的每行恰好一个好一个1和一个和一个-1, 其他元素都是其他元素都是0. 相当于关于相当于关于n个变量的个变量的m个差分约束个差分约束, 每个约束都形如每个约束都形如xj-
46、xi=bk, 其中其中1=i,j=n, 1=k=m.差分约束系统左边的可行性问题等价于右边的差分约束系统左边的可行性问题等价于右边的差分约束系统差分约束系统约束图约束图: 结点是变量结点是变量, 一个约束对应一条弧一个约束对应一条弧, 若有弧若有弧(u, v), 则则得到得到xu后后, 有有xv max then max:=xi; if yimax then max:=yi; end; n:=max; for i:=0 to n do begin new(headi); headi:=nil; end; for i:=0 to n-1 do begin new(p);p.dis:=1; p.k
47、ey:=i+1; p.next:=headi;headi:=p; end; for i:=n downto 1 do begin new(p); p.dis:=0; p.key:=i-1;p.next:=headi;headi:=p; end; for i:=1 to m do begin xi:=xi-1; new(p);p.dis:=-zi;p.key:=xi; p.next:=headyi; headyi:=p; end; k:=n; for i:=0 to n do begin disti:=huge; end; tail:=1; head1:=0; q1:=k; fillchar(f
48、,sizeof(f),true); distk:=0; fk:=false; while head1tail do begin inc(head1); u:=qhead1; p:=headu; while pnil do begin v:=p.key; if distu+p.dis2,就是说至除了出发点以外至少要经过就是说至除了出发点以外至少要经过2个其他不同的景个其他不同的景区，而且不能重复经过同一个景区。现在区，而且不能重复经过同一个景区。现在8600需要你帮他需要你帮他找一条这样的路线，并且花费越少越好。找一条这样的路线，并且花费越少越好。HDU1599：find the mincost
49、 routeInput：第一行是：第一行是2个整数个整数N和和M（N = 100, M = 1000)，代表景区的个数和道路的条数。代表景区的个数和道路的条数。接下来的接下来的M行里，每行包括行里，每行包括3个整数个整数a,b,c。代表。代表a和和b之间有之间有一条通路，并且需要花费一条通路，并且需要花费c元元(c k-v-(x1- x2- xm)- u(u与与k、k与与v都是直接相连的都是直接相连的)，其中，其中v -(x1- x2- xm)- u是指是指v到到u不经过不经过k的一种路径。的一种路径。HDU1599：find the mincost route在在u，k，v确定的情况下，要使
50、环权值最小，确定的情况下，要使环权值最小， 则要求则要求 (x1-x2- -xm)-u路径权值最小即要求其为路径权值最小即要求其为v到到u不经不经过过k的最短路径，则这个经过的最短路径，则这个经过u，k，v的环的最短路径就是：的环的最短路径就是：v到到u不包含不包含k的最短距离的最短距离+dist0，u，k+dist0，k，v。我们用我们用Floyd只能求出任意只能求出任意2点间满足中间结点均属于集合点间满足中间结点均属于集合1，2， ，k的最短路径，可是我们如何求出的最短路径，可是我们如何求出v到到u不包含不包含k的最短距离呢的最短距离呢?HDU1599：find the mincost r