图论刘汝佳.ppt

假设增广前s到u的距离为d(u), 增广后的费用函数为w(e), 对于弧e=uv定义一个新的权值w*(e) = w(e) + d(u) – d(v), 则对于任意s-t路X, 有w*(X) = w(X) – d(x), 即对于权函数w(e), w*(e), 从s出发的单源最短路树完全一样 改进算法: 用w*(e)=w(e)+d(u)-d(v)作为权函数计算单源最短路d*(x), 然后计算出真正的新最短路 注意到w*(e)是非负的, 所以可以用dijkstra实现. 为什么是非负的? 因为如果 w*(e)=w(e)+d(u)-d(v)0, 有d(v)d(u)+w(e) 和d(u)是最短距离矛盾 时间复杂度降为O(kn2), 稀疏图O(kmlogn) 应用：特殊二分图最佳匹配 每个X点有一个权值，最后要求所有被匹配到的X点的权和尽量大 算法：将X点按照权值从大到小排序，套用二分图最大基数匹配框架，先从权值大的点开始增广，得到的就是最优解 想一想，为什么 最小树型图 朱-刘算法（固定根） 首先消除自环，显然自环不在最小树形图中。然后判定是否存在最小树形图，以根为起点DFS一遍即可。 对于除根外的每个顶点，选择一条权最小的入边。如果选出来的V-1条边不构成环，则可以证明这些边就是满足要求的答案。否则收缩每个环，调整权值后求新图的最小树形图 4 5 3 -4 -3 -5 从新结点出去的边权不变 如果用了从外面进来的边，就得删除里面的边 最终答案加上人工点的权和 应用：举办比赛 给出一些有向边，边有带宽，还有一个修建费用，然后开始的时候你有cost钱问你怎么修建一个从0到达其他所有点的网络，使得所有网络中最小的带宽值最大 题目分析与讨论 1.太空旅行 太空里有n个星球，你的任务是用最少的步数从星球S到达星球T。每次可以从一个星球跳到另一个星球，但并不是所有n(n-1)种跳法都是可行的。所有顶点一共有k个“禁止区间”，其中每个禁止区间用(U, V1, V2)表示，即从星球U出发，不可以直接跳到V1, V1+1, V1+2, …, V2这些星球。 2.有向图D和E 给一个n个结点的有向图D，你可以构造这样一个图E：D的每条边对应E的一个结点（比如，若D有一条边uv，则E有个结点的名字叫uv），对于D的两条边uv和vw，E中的两个结点uv和vw之间连一条有向边。E中不包含其他边。给定图E，你的任务是判断是否存在对应的图D。 3.01串处理机 给M个长度为N的串，包含字符0,1或星号*。每个串最多包含一个星号。比如01*表示 010和011。用尽量少的指令处理所有串，其中每个指令也是一个长度为N，包含0,1或星号，且最多包含一个星号的串（指令10*处理100和101）。例如：{*01,100,011}至少需要两条指令10*和0*1。N=10, M=1000。 4.带宽难题 给一个无向图G，令T(u,v)为u到v的最大流流量。给定矩阵T，求满足条件的边数最少的无向图G。T(u,u)总是0，T(u,v)总是等于T(v,u)，且T(u,v)=10000。 5.我是SAM 给出一个RxC大小的网格，网格上面放了一些敌军目标，你可以在网格外发射子弹，只能沿着垂直或者水平方向发射，并且会打掉子弹路径上的所有敌军目标。现在需要，计算出最少需要多少子弹，从哪些位置发射，才能把所有的目标全部打掉。 6.爪分解 给一个简单无向图，每个点的度数均为3。你的任务是判断能否把它分解成若干个爪（即K1,3，如下图）。 每条边应恰好属于一个爪，同一个结点可以出现在多个爪里。 7.蚂蚁 给n个白点和n个黑点的坐标，要求用n条不相交的线段把它们连接起来，其中每条线段恰好连接一个白点和一个黑点，每个点恰好连接到一条线段。 8.鸽子和炸弹 给定一个n个点的连通的无向图，一个点的“鸽子值”定义为将它从图中删去后连通块的个数。求每个点的“鸽子值”。 9.少林决胜 给一个N x N矩阵，每个格子里都有一个正整数w(i,j)。你的任务是给每行确定一个整数row(i)，每列也确定一个整数col(i)，使得对于任意格子(i,j)，w(i,j)=row(i)+col(j)。所有row(i)和col(i)之和应尽量小。 10.出租车 你在一座城市里负责一个大型活动的接待工作。明天将有m位客人从城市的不同位置出发，到达他们各自的目的地，而且每人的出发时间已经提前给出。你的任务是用尽量少的出租车送他们，使得每次出租车接客人时，至少提前一分钟到达他所在的位置。注意，为了满足这一条件，要么这位客人是这辆出租车接送的第一个人，要么在接送完上一个客人后，有足够的时间从上一个目的地开到这里。 为了简单起见，假定城区是网格型的，地址用坐标(x,y)表示。出租车从(x1,y1)到(x2,y2)需要行驶|x