图论算法总结与图论建模

图的基本概念

第一页，共120页。图的基本概念二元组G(V,E)称为图(graph)。V为结点(node)或顶点(vertex)集。E为图中结点之间的边的集合。点，用数字0…n-1表示点对(u,v)称为边(edge)或称弧(arc)对于边(u,v)∈E -u和v邻接(adjacent) -e和u、v关联(incident)子图(subgraph):边的子集和相关联的点集第二页，共120页。图的基本概念有向图：边都是单向(unidirectional)的,因此边(u,v)是有序数对.有时用弧(arc)专指有向边带权图：可以给边加权(weight),成为带权图,或加权图(weightedgraph).权通常代表费用、距离等,可以是正数,也可以是负数稠密性：边和V(V-1)/2相比非常少的称为稀疏图(sparsegraph),它的补图为稠密图(densegraph)第三页，共120页。路径和圈一条路径(path)是一个结点序列,路上的相邻结点在图上是邻接的如果结点和边都不重复出现,则称为简单路径(simplepath).如果除了起点和终点相同外没有重复顶点和边,称为圈(cycle).不相交路(disjointpath)表示没有除了起点和终点没有公共点的路.更严格地

-任意点都不相同的叫严格不相交路(vertex-disjointpath) -同理定义边不相交(edge-disjointpath)路注意:汉语中圈和环经常混用(包括一些固定术语).由于一般不讨论自环(self-loop),所以以后假设二者等价而不会引起混淆第四页，共120页。连通性如果任意两点都有路径,则称图是连通(connected)的,否则称图是非连通的.非连通图有多个连通分量(connectedcomponent,cc),每个连通分量是一个极大连通子图(maximalconnectedsubgraph)第五页，共120页。完全图和补图完全图:N个顶点的图，有N(N-1)/2个节点对于(u,v),若邻接则改为非邻接,若非邻接则改为邻接,得到的图为原图的补图完全图=原图∪补图团：完全子图第六页，共120页。生成树树：N个点，N-1条边的连通图（无环连通图）生成树:包含某图G所有点的树一个图G是树当且仅当以下任意一个条件成立G有V-1条边,无圈G有V-1条边,连通任意两点只有唯一的简单路径G连通,但任意删除一条边后不连通第七页，共120页。图例第八页，共120页。图的表示方法介绍两种图的表示方法：邻接矩阵与邻接表V*V的二维数组A，A[i][j]=0,若(i,j)不相连，A[i][j]=1,若(i,j)相连图1图1的邻接矩阵表示第九页，共120页。邻接矩阵无向图的邻接矩阵是对称的优点：查找/删除某条边是O(1)的缺点遍历某一点的邻居是O(V)的空间复杂度很大，O(V*V)第十页，共120页。每个结点的邻居形成一个链表邻接表图2图2的邻接表表示第十一页，共120页。优点快速遍历某点所有邻居占用存储空间小，是O（边数）的，在稀疏图上的效率远胜邻接表缺点：查找/删除边不是常数时间邻接表第十二页，共120页。一、宽度优先遍历(BFS)二、深度优先遍历(DFS)图的遍历算法第十三页，共120页。给定图G和一个源点s,宽度优先遍历按照从近到远的顺序考虑各条边.算法求出从s到各点的距离宽度优先的过程对结点着色.白色:没有考虑过的点黑色:已经完全考虑过的点灰色:发现过,但没有处理过,是遍历边界依次处理每个灰色结点u,对于邻接边(u,v),把v着成灰色并加入树中,在树中u是v的父亲(parent)或称前驱(predecessor).距离d[v]=d[u]+1整棵树的根为s宽度优先遍历(BFS)第十四页，共120页。第十五页，共120页。题目大意：给出N*M个格子，给出K个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为1），如果两个湿的格子四联通（上下左右），则视为这两个格子同属于一个湖输入格式：第一行N，M，K接下来K个格子的坐标AvoidTheLakes（NOI题库2405）Input3453222312311Output4样例解释#....##.##..第十六页，共120页。新发现的结点先扩展得到的可能不是一棵树而是森林,即深度优先森林(Depth-firstforest)特别之处:引入时间戳(timestamp)发现时间d[v]:变灰的时间结束时间f[v]:变黑的时间1<=d[v]<f[v]<=2|V|深度优先遍历(DFS)第十七页，共120页。初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m)深度优先遍历(DFS)第十八页，共120页。括号结构性质对于任意结点对(u,v),考虑区间[d[u],f[u]]和[d[v],f[v]],以下三个性质恰有一个成立:完全分离u的区间完全包含在v的区间内,则在dfs树上u是v的后代v的区间完全包含在u的区间内,则在dfs树上v是u的后代DFS树的性质第十九页，共120页。定理(嵌套区间定理):在DFS森林中v是u的后代当且仅当d[u]<d[v]<f[v]<f[u],即区间包含关系.由区间性质立即得到.DFS树的性质第二十页，共120页。一条边(u,v)可以按如下规则分类树边(TreeEdges,T):v通过边(u,v)发现后向边(BackEdges,B):u是v的后代前向边(ForwardEdges,F):v是u的后代交叉边(CrossEdges,C):其他边，可以连接同一个DFS树中没有后代关系的两个结点,也可以连接不同DFS树中的结点判断后代关系可以借助定理1边的分类第二十一页，共120页。当(u,v)第一次被遍历,考虑v的颜色白色,(u,v)为T边灰色,(u,v)为B边(只有它的祖先是灰色)黑色:(u,v)为F边或C边.此时需要进一步判断d[u]<d[v]:F边(v是u的后代,因此为F边)d[u]>d[v]:C边(v早就被发现了,为另一DFS树中)时间复杂度:O(n+m)定理:无向图只有T边和B边(易证)边分类算法第二十二页，共120页。if(d[v]==-1)dfs(v);//树边,递归遍历elseif(f[v]==-1)show(“B”);//后向边elseif(d[v]>d[u])show(“F”);//前向边elseshow(“C”);//交叉边d和f数组的初值均为-1,方便了判断实现细节第二十三页，共120页。实现细节第二十四页，共120页。DAG:有向无环图拓扑顺序：拓扑排序算法第二十五页，共120页。对图G使用DFS算法,每次把一个结点变黑的同时加到链表首部ANEXAMPLE定理1:有向图是DAG当且仅当没有返祖边如果有返祖边,有环(易证)如果有环c,考虑其中第一个被发现的结点v,环中v的上一个结点为u,则沿环的路径vu是白色路径,u是v的后代,因此(u,v)是返祖边定理2:该算法正确的得到了一个拓扑顺序的逆序拓扑排序算法第二十六页，共120页。一、有向图:SCC划分的Kosaraju算法(有兴趣的同学自己看吧)二、有向图:SCC划分的Tarjan算法三、无向图:割顶和桥的判定图的连通性算法第二十七页，共120页。有向图中,u可达v不一定意味着v可达u.相互可达则属于同一个强连通分量(StronglyConnectedComponent,SCC)有向图和它的转置的强连通分量相同所有SCC构成一个DAGSCC的概念第二十八页，共120页。Tarjan算法是基于对图深度优先搜索的算法每个强连通分量为搜索树中的一棵子树搜索时，把当前搜索树中未处理的节点加入一个堆栈回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。tarjan算法(参考byvoid博客)第二十九页，共120页。定义：DFN(u)为节点u搜索的次序编号(时间戳)Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。dfn与low函数第三十页，共120页。算法伪代码tarjan(u){DFN[u]=Low[u]=++Index //为节点u设定次序编号和Low初值

Stack.push(u) //将节点u压入栈中

foreach(u,v)inE //枚举每一条边

if(visnotvisted) //如果节点v未被访问过

tarjan(v) //继续向下找

Low[u]=min(Low[u],Low[v])elseif(vinS) //如果节点v还在栈内

Low[u]=min(Low[u],DFN[v])if(DFN[u]==Low[u]) //如果节点u是强连通分量的根

repeatv=S.pop //将v退栈，为该强连通分量中一个顶点

printvuntil(u==v)}第三十一页，共120页。算法演示第三十二页，共120页。算法演示第三十三页，共120页。算法演示第三十四页，共120页。算法演示第三十五页，共120页。完整代码voidtarjan(inti){intj;DFN[i]=LOW[i]=++Dindex;instack[i]=true;Stap[++Stop]=i;for(edge*e=V[i];e;e=e->next){j=e->t;if(!DFN[j]){tarjan(j);if(LOW[j]<LOW[i])LOW[i]=LOW[j];}elseif(instack[j]&&DFN[j]<LOW[i])LOW[i]=DFN[j];}if(DFN[i]==LOW[i]){Bcnt++;do{j=Stap[Stop--];instack[j]=false;Belong[j]=Bcnt;}while(j!=i);}}voidsolve(){inti;Stop=Bcnt=Dindex=0;memset(DFN,0,sizeof(DFN));for(i=1;i<=N;i++)if(!DFN[i])tarjan(i);}第三十六页，共120页。N头奶牛(N≤10000)M对关系（a,b），表示a认为b是受欢迎的关系具有传递性，即若(a,b),(b,c)→(a,c)询问有多少头奶牛是被其他所有奶牛认为是受欢迎的PopularCows(POJ2186)第三十七页，共120页。求出所有的强连通分量每个强连通分量缩成一点，则形成一个有向无环图DAG。DAG上面如果有唯一的出度为0的点，则该点能被所有的点可达。那么该点所代表的连通分量上的所有的原图中的点，都能被原图中的所有点可达，则该连通分量的点数就是答案。DAG上面如果有不止一个出度为0的点，则这些点互相不可达，原问题无解，答案为0；PopularCows(POJ2186)第三十八页，共120页。proceduretarjan(u:longint);varp:node;v:longint;beginf[u]:=false;inc(top);stack[top]:=u;instack[u]:=true;p:=head[u];inc(time);dfn[u]:=time;low[u]:=time;whilep^.key<>udobeginv:=p^.key;iff[v]thenbegin

tarjan(v);

low[u]:=min(low[u],low[v]);endelsebeginifinstack[v]thenlow[u]:=min(low[u],dfn[v]);end;p:=p^.next;end;

iflow[u]=dfn[u]thenbegininc(s);whilestack[top]<>udobegininstack[stack[top]]:=false;jd[stack[top]]:=s;top:=top-1;end;instack[stack[top]]:=false;jd[stack[top]]:=s;top:=top-1;end;end;1.2.第三十九页，共120页。beginread(n);fori:=1tondobeginnew(head[i]);head[i]^.key:=i;head[i]^.next:=nil;end;read(m);s:=0;fori:=1tomdobeginread(edgex[i],edgey[i]);new(p);p^.key:=edgey[i];p^.next:=head[edgex[i]];head[edgex[i]]:=p;end;fillchar(f,sizeof(f),true);fillchar(instack,sizeof(instack),false);top:=0;time:=0;fori:=1tondoiff[i]thentarjan(i);fillchar(s1,sizeof(s1),0);

fori:=1tomdobeginifjd[edgex[i]]<>jd[edgey[i]]theninc(s1[jd[edgex[i]]]);end;s2:=0;s3:=0;fori:=1tosdoifs1[i]>0theninc(s2)elsebeginforj:=1tondoifjd[j]=itheninc(s3);end;ifs2+1=sthenwriteln(s3)elsewriteln(0);end.3.4.第四十页，共120页。对于无向连通图G割顶是去掉以后让图不连通的点桥是去掉以后让图不连通的边割顶与桥第四十一页，共120页。low[u]为u及其的后代所能追溯到的最早(最先被发现)祖先点v的dfn[v]值类似有向图的计算方式,注意无向图只有T和B边low[u]=dfn[u]=time++;for(u的不等于u的邻居v){//不考虑自环if(pre[v]==-1){//白色点dfs-visit(v);if(low[u]>low[v])low[u]=low[v];}elseif(low[u]>dfn[v])low[u]=dfn[v];}无向图的LOW函数第四十二页，共120页。在一棵DFS树中根root是割顶当且仅当它至少有两个儿子其他点v是割顶当且仅当它有一个儿子u,从u或者u的后代出发没有指向v祖先(不含v)的B边,则删除v以后u和v的父亲不连通,故为割顶割顶判定算法:对于DFS树根,判断度数是否大于1对于其他点u,如果不是根的直接儿子,且low[u]>=dfn[P[u]],则它的父亲v=P[u]是割点割顶的判定第四十三页，共120页。Network(POJ1144)voiddfs(intu,intdep){dfn[u]=low[u]=dep;for(inti=0;i<adj[u].size();i++){intv=adj[u][i];if(!dfn[v]){dfs(v,dep+1);if(u==rt)rt_son++;else{low[u]=min(low[u],low[v]);if(low[v]>=dfn[u])cut[u]=true; //由后继节点搜不到比该点更早的点，则该点是割点

}}elselow[u]=min(low[u],dfn[v]);}}题目大意：给定一个无向图，求有多少点是割点第四十四页，共120页。边(u,v)为桥当且仅当它不在任何一个简单回路中发现T边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的B边,则删除(u,v)后u和v不连通,因此(u,v)为桥桥的判定算法:发现T边(u,v)时若LOW[v]>d[u](注意不能取等号),则(u,v)为桥桥的判定第四十五页，共120页。Byteotia有n个镇。有的镇被双向的道路连接。每一对镇间最多只有一条直接连接的道路。任意两个镇连通。每个镇刚好有一个市民。他们为孤独所困。每个居民都想看看其他所有居民（去他所在的地方），而且刚好做一次。所以刚好发生了n*(n-1)次访问。不幸的是，一些程序员正在罢工，为了使软件的销售量提高。作为抗议活动的一部分，程序员想把Byteotia的一条道路关闭，阻止通过这条道路。他们正在辩论选择哪一条道路会使得后果最严重。（后果最严重即删去这条道路后访问次数最少）例题第四十六页，共120页。例题如图，若删去D,E之间的边，则会减少16次访问，若删去G,H之间的，会减少7次访问。若删除其它边，则不会减少访问次数。ACBGDFEH第四十七页，共120页。应该删除哪些边？很显然，只有删除桥才会减少访问次数，删去其它的边，图依然保持连通。因此，首先应该求出所有的桥。例题第四十八页，共120页。然后我们分别考虑每个桥的情况，删去这条边，会导致把图分成2个部分，而这两个部分是不连通的。考虑损失掉的访问，其实就是跨越这两个部分的访问，即|S1|*|S2|次访问，|S1|,|S2|是两个部分的大小。由此，大致的算法就形成了，枚举每一条边，然后计算损失的访问，最后输出答案即可。例题第四十九页，共120页。proceduretarjan(u:longint);varp:node;v:longint;beginf[u]:=false;inc(time);low[u]:=time;dfn[u]:=time;p:=head[u];whilep^.key<>udobeginv:=p^.key;iff[v]thenbeginfa[v]:=u;tarjan(v);low[u]:=min(low[u],low[v]);iflow[v]>dfn[u]thenbegininc(s);x1[s]:=u;y1[s]:=v;end;end

elseiffa[u]<>vthenlow[u]:=min(low[u],dfn[v]);p:=p^.next;end;end;functiondfs(u:longint):longint;beginf[u]:=false;p:=head[u];whilep^.key<>udobeginv:=p^.key;iff[v]thenbegintree[u]:=tree[u]+dfs(v);fa[v]:=u;end;p:=p^.next;end;inc(tree[u]);exit(tree[u]);end;1.2.第五十页，共120页。functioncount(x:longint):longint;beginwhilefa[x]<>0dox:=fa[x];count:=tree[x];end;beginread(n);fori:=1tondobeginnew(head[i]);head[i]^.key:=i;head[i]^.next:=nil;end;read(m);fori:=1tomdobeginread(x,y);new(p);p^.next:=head[x];p^.key:=y;head[x]:=p;new(p);p^.next:=head[y];p^.key:=x;head[y]:=p;end;

fillchar(f,sizeof(f),true);s:=0;fori:=1tondobeginiff[i]thenbegintime:=0;tarjan(i);end;end;fillchar(f,sizeof(f),true);fillchar(tree,sizeof(tree),0);fillchar(fa,sizeof(fa),0);fori:=1tondobeginiff[i]thentemp:=dfs(i);end;max:=0;

3.4.第五十一页，共120页。fori:=1tosdobeginc1:=tree[x1[i]];c2:=tree[y1[i]];ifc1>c2thenc3:=(count(c1)-tree[y1[i]])*tree[y1[i]]elsec3:=(count(c2)-tree[x1[i]])*tree[x1[i]];ifc3>maxthenbeginmax:=c3;x2:=x1[i];y2:=y1[i];end;end;writeln(max,'',x2,'',y2);end.5.第五十二页，共120页。给定一张连通图G（V,E）(V<=5,000，E<=10,000)询问至少要添加多少条边，使得，任意两点间至少有2条路径可达？RedundantPaths(POJ3177)第五十三页，共120页。RedundantPaths(POJ3177)ifdfn[u]=low[u]thenbegininc(s);whilestack[top]<>udobegininstack[stack[top]]:=false;

hash[stack[top]]:=s;stack[top]:=0;dec(top);end;instack[stack[top]]:=false;

hash[stack[top]]:=s;stack[top]:=0;dec(top);end;end;1.2.第五十四页，共120页。fillchar(map,sizeof(map),true);fillchar(s2,sizeof(s2),0);fori:=1tomdobeginif(hash[x[i]]<>hash[y[i]])and

(map[hash[x[i]],hash[y[i]]])thenbeginmap[hash[x[i]],hash[y[i]]]:=false;map[hash[y[i]],hash[x[i]]]:=false;inc(s2[hash[x[i]]]);inc(s2[hash[y[i]]]);end;end;s1:=0;fori:=1tosdoifs2[i]=1theninc(s1);writeln((s1+1)div2);end.3.4.第五十五页，共120页。图的最短路问题

SSSP的Spfa算法SSSP的Dijkstra算法差分约束系统Floyd-warshall算法第五十六页，共120页。给定带权图和一个起点s,求s到所有点的最短路(边权和最小的路径)最短路有环吗正环:何必呢,删除环则得到更短路负环:无最短路,因为可以沿负环兜圈子单源最短路问题(SingleSourceShortestPath)第五十七页，共120页。最优性原理:若最短路uv经过中间结点w,则uw和wv的路径分别是u到w和w到v的最短路意义:贪心、动态规划最优性原理第五十八页，共120页。最短路的表示s到所有点的最短路不需要分别表示最短路树:到每个点都沿着树上的唯一路径走实际代码:记录每个点的父亲pred[u]即可输出最短路:从终点沿着pred[u]递推回起点最短路的表示第五十九页，共120页。松弛（RELAX）操作一条边(u,v)被称为紧的(tense),如果dist(u)+w(u,v)<dist(v)可以松弛：dist(v)=dist(u)+w(u,v),pred(v)=u结论存在紧的边，一定没有正确的求出最短路树不存在紧的边，一定正确的求出最短路树SPFA算法第六十页，共120页。SPFA算法伪代码第六十一页，共120页。SPFA算法优点：如其名，快速。期望的时间复杂度：O(ke)，其中k为所有顶点进队的平均次数，可以证明k一般小于等于4。有兴趣自己GOOGLE解决><写起来很方便缺点：在网格图上的效率很低，接近O（n^2）第六十二页，共120页。POJ3259-Wormholes题目大意：虫洞问题，现在有n个点，m条边，代表现在可以走的通路，比如从a到b和从b到a需要花费c时间，现在在地上出现了w个虫洞，虫洞的意义就是你从a到b花费的时间是-c(时间倒流,并且虫洞是单向的)，现在问你从某个点开始走，能否回到从前第六十三页，共120页。POJ3259-Wormholes提示：SPFA其实是Bellman-ford算法的优化而Bellman-ford可以用来判断一张图中是否存在负环判断方法为：如果一个点被松弛了n次，那么图中就存在负环第六十四页，共120页。POJ3259-Wormholes题解：按照题目意思建图，判断图中是否存在负环，存在即可回到过去。第六十五页，共120页。把顶点集合V分成两组：（1）S：已求出的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定的顶点集合Dijkstra算法（仅适用于无负权边的情况）第六十六页，共120页。将T中顶点按递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点距离：从V0到此顶点的最短距离T中顶点距离：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度Dijkstra算法（仅适用于无负权边的情况）第六十七页，共120页。正确性证明算法流程Dijkstra算法第六十八页，共120页。Dijkstra算法使用了一个优先队列INSERT(line3),每个结点一次EXTRACT-MIN,每个结点一次DECREASE-KEY(line8,在RELAX过程中),一共|E|次直接实现:O(V2)二项堆:O(ElogV)Fibonacci堆:O(E+VlogV)时间复杂度第六十九页，共120页。在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：1．路径上的所有点的出边所指向的点都直接或间接与终点连通。2．在满足条件1的情况下使路径最短。注意：图G中可能存在重边和自环，题目保证终点没有出边。请你输出符合条件的路径的长度。NOIP2014Day2T2寻找道路第七十页，共120页。输入格式：第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为tNOIP2014Day2T2寻找道路第七十一页，共120页。Input

66

12

13

26

25

45

34

15Output3NOIP2014Day2T2寻找道路如上图所示，满足条件的路径为1->3->4->5。注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。第七十二页，共120页。大致思路：因为路径上的所有点的出边所指向的点都直接或间接与终点连通，所以我们不妨把所有的边反向，然后求t到s的最短路径大致证明：先将所有边按照读入顺序标号所有满足条件1的从s到t路径，在边都反向的情况下，对应一条t到s的路径，并且满足一一对应（因为路径上边的标号都相同）Tips：这里的最短路可以BFS求得（因为路径长度都是1）NOIP2014Day2T2寻找道路第七十三页，共120页。begin//主程序read(n,m1);fori:=1tondobeginnew(head[i]);head[i]:=nil;new(head1[i]);head1[i]:=nil;end;fori:=1tom1doread(x[i],y[i]);read(a,b);sort(1,m1);m:=0;fillchar(f,sizeof(f),true);x1:=0;y1:=0;fillchar(s,sizeof(s),0);fori:=1tom1dobeginifx[i]=y[i]thenf[x[i]]:=falseelsebeginif(x[i]=x1)and(y[i]=y1)thencontinue;inc(s[x[i]]);inc(m);x1:=x[i];y1:=y[i];new(p);p^.key:=y1;p^.next:=head[x1];head[x1]:=p;new(p);p^.key:=x1;p^.next:=head1[y1];head1[y1]:=p;end;end;proceduredfs1(u:longint);//子程序varp:node;v:longint;beginf[u]:=false;p:=head1[u];whilep<>nildobeginv:=p^.key;iff[v]thenbegininc(s1[v]);f[v]:=false;dfs1(v);endelseinc(s1[v]);p:=p^.next;end;end;1.2.第七十四页，共120页。fillchar(s1,sizeof(s1),0);fillchar(f,sizeof(f),true);dfs1(b);fillchar(al,sizeof(al),true);fori:=1tondobeginifi=bthencontinue;ifs[i]<>s1[i]thenal[i]:=false;end;find:=false;head2:=0;tail:=1;fillchar(q,sizeof(q),0);q[1].key:=a;q[1].dist:=0;fillchar(f,sizeof(f),true);f[a]:=false;whilehead2<taildobegininc(head2);u:=q[head2].key;p:=head[u];whilep<>nildobeginv:=p^.key;if(f[v])and(al[v])thenbeginf[v]:=false;inc(tail);q[tail].key:=v;q[tail].dist:=q[head2].dist+1;ifv=bthenbeginwriteln(q[tail].dist);find:=true;break;end;end;p:=p^.next;end;iffindthenbreak;iffind=falsethenwriteln(-1);end.3.4.第七十五页，共120页。线性规划(linearprogramming,LP):给m*n矩阵A、m维向量b和n维向量c,求出x为向量使得Ax<=b,且sum{cixi}最小可行性问题(feasibilityproblem):只需要任意找出一组满足Ax<=b的解向量x差分约束系统(systemofdifferenceconstraints):A的每行恰好一个1和一个-1,其他元素都是0.相当于关于n个变量的m个差分约束,每个约束都形如xj-xi<=bk,其中1<=i,j<=n,1<=k<=m.差分约束系统第七十六页，共120页。左边的可行性问题等价于右边的差分约束系统差分约束系统第七十七页，共120页。约束图:结点是变量,一个约束对应一条弧,若有弧(u,v),则得到xu后,有xv<=xu+w(u,v)差分约束系统第七十八页，共120页。定理:如果约束图没有负圈,则可取xu为起点v0到u的最短路长;若约束图有负圈,差分约束系统无解.正确性证明无负圈:由松弛条件可证明每个约束得到满足有负圈:把负圈上的约束条件叠加将得到一个矛盾不等式算法步骤构图,得到n+1个结点m+n条边运行最短路算法差分约束系统第七十九页，共120页。N个区间，[ai,bi]问一个整数的集合Z至少需要多少个元素，使得，在第i个区间的范围内至少有ci个整数属于集合Z。SampleInput SampleOutput6IntervalsPOJ1201第八十页，共120页。beginread(m);max:=0;fori:=1tomdobeginread(x[i],y[i],z[i]);ifx[i]>maxthenmax:=x[i];ify[i]>maxthenmax:=y[i];end;n:=max;fori:=0tondobeginnew(head[i]);head[i]:=nil;end;fori:=0ton-1dobeginnew(p);p^.dis:=1;p^.key:=i+1;p^.next:=head[i];head[i]:=p;end;

fori:=ndownto1dobeginnew(p);p^.dis:=0;p^.key:=i-1;p^.next:=head[i];head[i]:=p;end;fori:=1tomdobeginx[i]:=x[i]-1;new(p);p^.dis:=-z[i];p^.key:=x[i];p^.next:=head[y[i]];head[y[i]]:=p;end;k:=n;fori:=0tondobegindist[i]:=huge;end;tail:=1;head1:=0;q[1]:=k;fillchar(f,sizeof(f),true);dist[k]:=0;f[k]:=false;

1.2.第八十一页，共120页。whilehead1<taildobegininc(head1);u:=q[head1];p:=head[u];whilep<>nildobeginv:=p^.key;ifdist[u]+p^.dis<dist[v]thenbegindist[v]:=dist[u]+p^.dis;iff[v]thenbegininc(tail);q[tail]:=v;f[v]:=false;end;end;p:=p^.next;end;f[u]:=true;end;writeln(abs(dist[0]));end.3.第八十二页，共120页。目标：给定图G，求出任意两点的最短路径动态规划的思想设d[i,j,k]是在只允许经过结点1…k的情况下i到j的最短路长度则它有两种情况（想一想，为什么）：最短路经过点k，d[i][j][k]=d[i][k][k-1]+d[k][j][k-1]最短路不经过点k，d[i][j][k]=d[i][j][k-1]Floyd-warshall算法第八十三页，共120页。编程复杂度低，三重循环注意：外层循环是KFloyd-warshall算法第八十四页，共120页。注意“无穷大”的运算时间复杂度:O(n^3)空间复杂度:O(n^2)Floyd-warshall算法第八十五页，共120页。杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,....VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。HDU1599：findthemincostroute第八十六页，共120页。Input：第一行是2个整数N和M（N<=100,M<=1000)，代表景区的个数和道路的条数。

接下来的M行里，每行包括3个整数a,b,c。代表a和b之间有一条通路，并且需要花费c元(c<=100)。Output：对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如果找不到的话，输出“It’simpossible.”。HDU1599：findthemincostroute第八十七页，共120页。floyd求最小环:抛开Dijkstra算法，进而我们想到用Floyd算法。我们知道，Floyd算法在进行时会不断更新矩阵dist(k)。设dist[k，i，j]表示从结点i到结点j且满足所有中间结点，它们均属于集合{1，2，⋯，k}的一条最短路径的权。其中dist[0,i,j]即为初始状态i到j的直接距离。对于一个给定的赋权有向图，求出其中权值和最小的一个环。我们可以将任意一个环化成如下形式：u->k->v->(x1->x2->⋯xm)->u(u与k、k与v都是直接相连的)，其中v->(x1->x2->⋯xm)->u是指v到u不经过k的一种路径。HDU1599：findthemincostroute第八十八页，共120页。在u，k，v确定的情况下，要使环权值最小，则要求(x1->x2->⋯->xm)->u路径权值最小．即要求其为v到u不经过k的最短路径，则这个经过u，k，v的环的最短路径就是：[v到u不包含k的最短距离]+dist[0，u，k]+dist[0，k，v]。我们用Floyd只能求出任意2点间满足中间结点均属于集合{1，2，⋯，k}的最短路径，可是我们如何求出v到u不包含k的最短距离呢?

HDU1599：findthemincostroute第八十九页，共120页。现在我们给k加一个限制条件：k为当前环中的序号最大的节点(简称最大点)。因为k是最大点，所以当前环中没有任何一个点≥k，即所有点都<k。因为v->(x1->x2->......xm)->u属于当前环，所以x1，x2，⋯，xm<k，即x1，x2⋯xm≤k-1。这样，v到u的最短距离就可以表示成dist[k-1,u,v]。dist[k-1,v,u]表示的是从v到u且满足所有中间结点均属于集合{1，2，⋯，k-1}的一条最短路径的权。接下来，我们就可以求出v到u不包含k的最短距离了。这里只是要求不包含k，而上述方法用的是dist[k-1，v，u]，求出的路径永远不会包含k+1，k+2，⋯HDU1599：findthemincostroute第九十页，共120页。万一所求的最小环中包含k+1，k+2，⋯怎么办呢?的确，如果最小环中包含比k大的节点，在当前u,k,v所求出的环显然不是那个最小环。然而我们知道，这个最小环中必定有一个最大点k0，也就是说，虽然当前k没有求出我们所需要的最小环，但是当我们从k做到k0的时候，这个环上的所有点都小于k0了．也就是说在k=k0时一定能求出这个最小环。HDU1599：findthemincostroute第九十一页，共120页。我们用一个实例来说明：假设最小环为1—3—4—5—6—2—1。的确，在u=1，v=4，k=3时，k<6，dist[3，4，1]的确求出的不是4—5—6—2—1这个环，但是，当u=4，v=6，k=5或u=5，v=2，k=6时，dist[k，v，u]表示的都是这条最短路径.所以我们在Floyd以后，只要枚举u．v，k三个变量即可求出最小环。时间复杂度为O(n3)。我们可以发现，Floyd和最后枚举u，v，k三个变量求最小环的过程都是u,v,k三个变量，所以我们可以将其合并。这样，我们在k变量变化的同时，也就是进行Floyd算法的同时，寻找最大点为k的最小环。HDU1599：findthemincostroute第九十二页，共120页。最小生成树（MST,MinimalSpanningTree）

PRIM算法并查集KRUSKAL算法第九十三页，共120页。给定图G求连接每个点的连通图（一定是树）权和尽量小最小生成树第九十四页，共120页。假设选取若干条边，使得当前的图被分成了若干个连通分量无用边：边的两个端点属于同一个连通分量，但这条边不属于任意一个连通分量安全边：从它出去(即恰好有一个端点在此分量内)的最小边不同的分量可以有相同的安全边结论:MST含有所有安全边,不含无用边.最小生成树思想第九十五页，共120页。结论:MST含有所有安全边,不含无用边.证明假设有一个分量(黄色),它的安全边e不在T内.则u到v有唯一路径,它经过e’,它恰好有一个端点在黄色分量中.由于e是安全边,w(e)<w’(e),用e替换e’得到更小的T’,矛盾加入无用边将形成环最小生成树思想第九十六页，共120页。只关心一棵树T,每次加入T的安全边用堆保存到每个顶点(而非边)的安全边Insert/ExtractMin调用V次,DecreaseKey调用E次二叉堆:O((E+V)logV),Fibonacci堆:O(E+VlogV)PRIM算法第九十七页，共120页。PRIM算法第九十八页，共120页。将编号分别为1…N的N个对象划分为不相交集合在每个集合中，选择其中某个元素代表所在集合常见两种操作：合并两个集合查找某元素属于哪个集合并查集DisjointSet第九十九页，共120页。每个集合用一棵“有根树”表示定义数组fa[1..n]fa[i]=i，则i表示本集合，并是集合对应树的树根set[i]=j,j<>i,则j是i的父节点并查集DisjointSet123456789101232134334iSet(i一百页，共120页。查询x所在集合根节点 合并集合a,b并查集DisjointSetfind(x){ while(fa[x]!=x)x=fa[x]; returnx;}最坏情况Θ(logN)merge(a,b){ if(height(a)==height(b)){ height(a)=height(a)+1; fa[b]=a; } elseif(height(a)<height(b))fa[a]=b; elsefa[b]=a;}Θ(1)第一百零一页，共120页。思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快步骤:第一步，找到根结点第二步，修改查找路径上的所有节点，将它们都指向根结点路径压缩优化find(x){ while(x!=fa[x])fa[x]=find(fa[x]); returnfa[x];}第一百零二页，共120页。路径压缩优化9108122021164611164111101298202116第一百零三页，共120页。Kruskal,1956年提出把边从小到大排序,每次填加一个安全边如何知道边是否安全?并查集,每次约O(1)总O(ElogE+Eα(V))Kruskal算法第一百零四页，共120页。在二维平面上有N个村庄，坐标（xi,yi）给定为其中的S个村庄配备卫星通信设备，使得配备了卫星通信的村庄间互相都能沟通为每个村庄配备一个无线电，能使其能与距离不超过D的村庄沟通求一种卫星通信设备的分配方案，使得D最小，并且满足任意两个村庄之间能沟通，直接或间接ArcticNetworkPOJ2349第一百零五页，共120页。SampleInputSampleOutput212.13ArcticNetworkPOJ2349第一百零六页，共120页。假设d已知，把所有铺设线路的村庄连接起来，构成一个图。需要卫星设备的台数就是图的连通支的个数。d越小，连通支就可能越多。那么，只需找到一个最小的d，使得连通支的个数小于等于卫星设备的数目。ArcticNetworkPOJ2349第一百零七页，共120页。把整个问题看做一个完全图，村庄就是点，图上两点之间的边的权值，就