当前位置:首页 >> >>

NOI导刊-图论模型的构建_图文

图论模型的构建

NOIP若干图论的考题
? Core(2007) :图的多源最短路算法及其简单 处理
? 双栈排序(2008):栈的应用+二分图的搜索 ? 最优贸易(2009):基本图论

问题:求网线线序

? 网线从机房连接到办公室

? 在机房,所有网线从左到右 编号为1,2,3,…,N

? 给出每两条线是否交叉的信

(a)

息,请计算办公室内从左到

右各条线的编号

(b)

选址问题
? 现准备在 n 个居民点v1, v2, … , vn中设置一银 行.问设在哪个点,可使最大服务距离最小? 若设置两个银行,问设在哪两个点?
? 模型假设 假设各个居民点都有条件设置 银行,并有路相连,且路长已知.

模型建立与求解

? 用Floyd算法求出任意两个居民点vi , vj 之间的最短距离,并 用dij 表示.
⑴ 设置一个银行,银行设在 vi 点的最大服务距离为
di ? m1?aj?xn{dij}, i ? 1,2,..., n.

求k,使 dk ? m1?ii?nn{di}.

即若设置一个银行,则银行设在 vk 点,可使最大服务距离最小.

⑵ 设置两个银行,假设银行设在vs , vt 点使最大服务距离最小.



d (i,

j)

?

max{min{
1?k ?n

dik , d jk}}.

则s,t 满足:d(s,t) ? min {d(i, j)}. 1?i? j?n

进一步,若设置多个银行呢?

求k,使

dk

?

min
1?i?n

{d

i

}.

即若设置一个银行,则银行设在 vk 点,可使最 大服务距离最小.

⑵ 设置两个银行,假设银行设在vs , vt 点使 最大服务距离最小.



d

(i,

j)

?

max{min{
1?k ?n

dik

,

d

jk}}.

则s,t 满足:

d(s,t) ? min {d (i, j)}. 1?i? j?n

进一步,若设置多个银行呢?

最优贸易
? 某国有M个城市N条道路,任意两个城市有道路,有一部 分道路为单行线,一部分为双向道路。
? 某人去该国旅游,从城市1出发到城市n结束,他想做水晶 球的生意一次挣点旅行费用,每个城市有一个水晶球的价 格(买入卖出都一样),他可以经过每个城市多次。
? 问他能挣最多的费用为多少? ? 如下图,假设城市1~5的价格为4,3,5,6,1 ? 则选择1-4-5-4-5路线,
挣得5

分析
? 这是一道非常典型的图论题, 如果有扎实的图论基础解决 起来并不困难.
? 解决这道题的关键是发现, 我们可以将原图中的任意一个 强连通分量收缩为一个点, 这个新点的买入价格等于该强 连通分量中最小的买入价格, 这个新点的卖出价格等于该 强连通分量中最大的卖出价格. 这是因为, 这个新点的性质 和一个强连通分量是一样的, 如果我们要在一个强连通分 量中进行购买操作, 一定会选择买入价格最小的那个点, 如 果我们要在一个强连通分量中进行卖出操作, 也一定会选 择卖出价格最大的那个点.
?

分析
? 所以算法就非常清晰了. 首先利用DFS将所有的强连通分量 收缩, 这样我们就可以得到一个有向无环图G. 由于G中没 有环, 我们可以对G进行拓扑排序, 然后利用递推求得到达 某个点i时, 可能的最低买入价格best(i)是多少, 以及该点最 终能否到达终点. 最后对于所有能够到达终点的点p, 设其 卖出价格为sell(p), 在sell(p)-best(p)中取最大值即得到答案. 时间复杂度仅为O(V+E).
?
? 在实现的时候最好使用栈消除DFS中的递归调用, 因为图中 的点可以达到100000, 当递归深度达到这么大的时候有相 当大的几率发生栈溢出. 参考实现中采用了非递归实现DFS.

奇怪的电梯
? 大楼的每一层楼都可以停电梯,而且第i层楼(1<=i<=N)上 有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮:开,关, 上,下。上下的层数等于当前楼层上的那个数字。当然, 如果不能满足要求,相应的按钮就会失灵。例如:3 3 1 2 5代表了Ki(K1=3,K2=3,……),从一楼开始。在一楼,按“上” 可以到4楼,按“下”是不起作用的,因为没有-2楼。那么, 从A楼到B楼至少要按几次按钮呢?
? 输入: 二行,第一行为三个用空格隔开的正整数,表示 N,A,B(1≤N≤200, 1≤A,B≤N),第二行为N个用空格隔开的正 整数,表示Ki。
? 输出:仅一行,即最少按键次数,若无法到达,则输出-1。

构图
LIFT.IN 515 33125 LIFT.OUT 3
? 对于A楼而言,实际上对它最多只能做2个操作,上到A+X 层或下到A-X层,当然前提是存在A+X或A-X层。显然,如 果把每一层楼看做一个顶点,如果A楼可以到B楼,则从 顶点A引一条到顶点B的边,这样一来,问题就变成了图 论中的两顶点间最短路径问题了!当然权设为1就行了。

人穿柱子游戏
? 在一个无限长的条形路上,有n(n<=200)个 柱子,体积不计,有一个人想从左边走到 右边,人近似看成一个半径为R的圆(如下 图),问能否实现?

构图
? 每个圆的大小完全相同,不存在包含,相切(如 果内切,就是重合了,如果外切,就是中间不连 通的)等等复杂的关系,只有相交和相离的关系, 而且如果2个圆之间相交的话,那么这2个圆就是 相通的,可以在这2个圆的圆心之间连一条边,增 加一个源点,与上边有交点的圆和源点连一条边, 增加一个汇点,与下边有交点的圆和汇点连一条 边,这样就把一道几何题完全转换成了一道图论 题,只要判断源点和汇点之间是否有路就可以了

奇怪的数列
? 编程输入3个整数n,p,q,寻找一个由整数组成的 数列(a1,a2,……,an),要求:其中任意连续p 项之和为正数,任意连续q项之和为负数。0<n<100, 0<p,q<n,若不存在这样的整数数列,则输出NO; 否则输出满足条件的一个数列即可。
? 输入格式: 仅一行分别表示n,p,q,之间用一个空格隔开。
? 输出格式: 只有一行,有解即输出这个数列,每个数之间用一 个空格隔开。否则输出NO。

分析

? 如果我们按常规思想,直接将第i个整数ai开始的k个整数 之和描述成多项式ai+ai+1+…+ai+k-1的话,问题就很难再往下 思考和解决了。所以,我们不防换个角度,暂且撇去每一

项数究竟为何值的具体细节,而将注意力集中至连续性这

一特点上。设si表示数列前i个整数之和,即si=a1+a2+…+ai。 其中s0=0 (0≤i≤n)。显然根据题意,有:

si<si+p

(0≤i≤n-p)

si+q<si

(0≤i≤n-q)

? 下面,我们把每个si抽象成一个点,则根据上述两个不等 式可以建立一个有向图,图中共有n+1个顶点,分别为s0, s1,……,sn。若si>sj(0≤i,j≤n),则从si往sj引出一条有向边。

构图
? 对于n=6,p=5,q=3的情况,我们可以建立 下图:

? 对图进行拓扑排序; if 图有回路 then 无解退出 else 生成拓扑序列order[0]…order[n];
? 那么如果得到了一个拓扑序列,该如何转换成s数组呢?因为拓扑序列 中顶点对应的s值是递减的,其中s0=0。
? 如果order[i]=0,则依次设定sorder[0]=i,sorder[1]=i-1,……,sorder[i-1]=1, sorder[i]=0,sorder[i+1]=-1,……,sorder[n]=i-n。
? 例如,对于上图所示的有向图,可以得到下表:
? 所以,得到s0=0,s1=-3,s2=2,s3=-1,s4=-4,s5=1,s6=-2。再根据s的 定义,由: ai=(a0+a1+…+ai-1+ai) - (a0+a1+…+ai-1)=si-si-1 ,求出:a1=s1s0=-3,a2=s2-s1=5,a3=s3-s2=-3,a4=s4-s3=-3,a5=s5-s4=5,a6=s6-s5=-3。显 然这个整数数列的任意连续5个整数之和为正,任意连续3个整数之 和为负。

牧场规划
? 小可可的好朋友Sealock最喜欢吃花生了,于是借用了 小可可的牧场从事花生选种试验。他以网格的方式,非 常规整地把牧场分割成M*N个矩形区域(M*N≤5000), 由于各个区域中地水面、沼泽面积各不相同,因此各区 域地实际可种植面积也各不相同,已知区域(i,j)地可种 面积使A(i,j)。
? 每个区域种最多只能种植一个品种地花生。可种植面积 为零地区域不能被选择用来从事选种试验,同时为了防 止花粉传播到相邻区域造成试验结果不正确,任何两个 相邻的区域都不可以同时种植花生。这里说的相邻指的 是两个区域有公共边,仅仅有公共点的两个区域不算做 相邻。
? 小可可准备帮助Sealock规划一下如何选择种植区域, 才能使得实际可种植面积总和最大。

构图
? 将试验田转化为点、并连接相邻的试验田后可以发现,我们得到的是 一个二分图。通过对原图的黑白染色,可以把其中的一部分称为白点、 另一部分称为黑点。由二分图建立网络:加入源点和汇点,从源点向 每个白点引一条边,容量为白点对应试验田的面积;从每个黑点向汇 点引边,容量为该黑点的对应面积。最后将相邻点之间的边改为网络 中的边,由白点指向黑点,容量为正无穷。通过求网络最大流得到它 的最小割,即为最优方案。
S T
图1 建立网络

和平委员会(SPO)
? 要选一个委员会,但是出现了一个问题,某些代表是有矛盾 的,不能同时选到委员会里来。现在有n个政党,每个政党 只有两个代表,要从每个政党中选择一个代表,使委员会里 的人都是友好的。所有的人用1到2n来编号,2i-1 和 2i属于同 一个政党。
? 读入政党总数,以及不友好的人的对数。
? 计算是否可以建立委员会。如果可以,给出方案。
? 输入:第一行有两个整数n和m,1<=n<=8000,0<=m<=20000。 分别表示政党的总数以及不友好的关系数。接下来的m行, 每行整数a 和 b, 1<=a<b<=2n,表示这两个人是有矛盾的。
? 输出:无解则输出NIE。否则打印n行,从小到大输出你的方 案中各人的编号。任意可行解都是可以的。

分析:
? 原题可描述为: 有n个组,第i个组里有两个节点Ai, Ai' 。需要从每个 组中选出一个。而某些点不可以同时选出(称之为 不相容)。任务是保证选出的n个点都能两两相容。
– (在这里把Ai, Ai' 的定义稍稍放宽一些,它们同 时表示属于同一个组的两个节点。也就是说,如 果我们描述Ai,那么描述这个组的另一个节点就 可以用Ai')

初步构图

? 如果Ai与Aj不相容,那么如果选择了Ai,必须选择 Aj‘ ;同样,如果选择了Aj,就必须选择Ai’ 。

Ai

Aj'

Aj

Ai‘

这样的两条边对称

? 我们从一个例子来看:

? 假设4个组,不和的代表为:1和4,2和3,7和3, 那么构图:

1

3

5

7

2

4

6

假设:
首先选1 ?3必须选,2不可选 ?8必须选,4、7不可选

8
5、6可以任选一个

1

3

5

7

2

4

? 矛盾的情况为:

6

8

存在Ai,使得Ai既必须被选又不可选。

? 得到算法1:
? 枚举每一对尚未确定的Ai, Ai‘ ,任选1个,推导出 相关的组,若不矛盾,则可选择;否则选另1个, 同样推导。若矛盾,问题必定无解。

? 此算法正确性简要说明: ? 由于Ai,Ai' 都是尚未确定的,它们不与之前的组相
关联,前面的选择不会影响Ai, Ai' 。
? 算法的时间复杂度在最坏的情况下为O(nm)。 ? 在这个算法中,并没有很好的利用图中边的对称


? 先看这样一个结构: ? 更一般的说:

1

3

? 在每个一个环里,任意一

5

7

个点的选择代表将要选择

此环里的每一个点。不妨

2

4

把环收缩成一个子节点

6

8

(规定这样的环是极大强

连通子图)。新节点的选

此图中1和3构成一个环, 这样1和3要么都被选择, 要么都不被选。

择表示选择这个节点所对 应的环中的每一个节点。

2和4同样如此。

图的收缩

? 对于原图中的每条边Ai Aj(设Ai属于环Si,Aj属于 环Sj)如果Si≠Sj,则在新图中连边:

Si

Sj

1

3

5

7

S1

S2

S3

2

4

6

8

S1'

S2'

S3'

? 这样构造出一个新的有向无环图。 ? 此图与原图等价。

图的收缩

算法2
? 通过求强连通分量,可以把图转换成新的有向无环图, 在这个基础上,介绍一个新的算法。
? 新算法中,如果存在一对Ai, Ai‘属于同一个环,则判无解, 否则将采用拓扑排序,以自底向上的顺序进行推导,一 定能找到可行解。

算法2的流程:
? 1.构图 ? 2.求图的极大强连通子图 ? 3.把每个子图收缩成单个节点,根据原图关系构造一
个有向无环图 ? 4.判断是否有解,无解则输出(退出) ? 5.对新图进行拓扑排序 ? 6.自底向上进行选择、删除 ? 7.输出

瘦陀陀和胖陀陀
? 一场可怕的战争后,瘦陀陀和他的好朋友胖陀陀 将要凯旋。
– 瘦陀陀处在城市A – 胖陀陀处在另外一个未知的城市 – 他们打算选一个城市X(这个由瘦陀陀来决定) – 胖陀陀会赶在瘦陀陀之前到达城市X – 然后等待瘦陀陀也赶到城市X与他汇合,并举办一次庆
祝宴会(由瘦陀陀请客) – 接着一起回到他们的家乡城市B – 由于胖陀陀嘴馋,他要求举办宴会的城市必须是瘦陀
陀回家的路线中举办宴会最贵的一个城市。

一个例子(续)
? 瘦陀陀正专注地看回家的地图 – 地图上标有n(n≤200)个城市 和某些城市间直达的道路 – 以及每条道路的过路费 – 瘦陀陀还知道在每一座城市举 办宴会的花费。
? 给出地图和A、B的位置 – 请你告诉瘦陀陀回家的最小费 用 – 你的程序会接收到多次询问 – 即对于每对城市(c1,c2),你的 程序应该立刻给出瘦陀陀从c1 到c2的最小花费。

分析
? 胖陀陀规定必须在最贵的城市举办宴会
– 因此不能简单地选择一条最短路走 – 若路上有一个花费特别贵的城市…
? 对于每个点X,如果在那里办宴会…
– 如何求最短路? – 多个询问怎么处理?
? floyd计算每两点的距离? ? SSSP就可以胜任吗?
– AB = AX + XB…

树网的核
? 给出一棵无根树,边上有权。称树的最长 路径为直径,定义路径的偏心距为:点到 路径的上的点的最小值的最大值,给出一 个s,找出直径上的某段长度不超过s的路径, 使得偏心距最小。

分析
? 考虑到树的性质,对于任意两点,最短路=联通路=最长 路。 首先用floyd算法求出任意两点之间最短路。同时可以求 出最长路径上都有哪些点。由于这是一棵树,最短路必 然唯一。设mid[a,b]是a,b之间的联通路上的一个中间点。 考虑问题的解,构造一个函数F(k,a,b)为K到ab间的最短 路的长度。则
? f(k,a,b)=min{d[k,mid[a,b],f[k,a,mid[a,b]],f[k,mid[a,b],b]} ? 写出了这个方程,便不难得出一个三次方的算法。在实
际做的时候,可以把k放在最外层枚举,这样内层实际上 只用到了f的后面2维,用2维数组记录即可。

双栈排序
? 有两个队列和两个栈,分别命名为队列1(q),队列2(q2), 栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q中 有n个数(n<=1000),为1~n的某个排列. 现在支持如下四种操作: ?a操作,将 q的首元素提取出并加入s1的栈顶. ? b操作,将s1的栈顶元素弹出并加入q2的队列尾. ?c操作,将 q的首元素提取出并加入s2的栈顶. ? d操作,将s2的栈顶元素弹出并加入q2的队列尾.
? 请判断,是否可以经过一系列操作之后,使得q2中依次 存储着1,2,3,…,n.如果可以,求出字典序最小的一个操 作序列.

考虑单栈

例1:1,2,3,4,5 yes例; 2:5,4,3,2,1 yes; 例3:3,2,4,5,1 yes;例4:3,1,4,5,2 no;

5,4,3,2,1

1,2,3,4,5

B

A

C

定理
? 定理:对于任意两个数q[i]和q[j]来说,它们不能压入同一 个栈中的充要条件p是:存在一个k,使得i<j<k且 q[k]<q[i]<q[j].
? 充分性:即如果满足条件p,那么这两个数一定不能压入 同一个栈.这个结论很显然,使用反证法可证. 假设这两个数压入了同一个栈,那么在压入q[k]的时候栈 内情况如下: …q[i]…q[j]… 因为q [k]比q [i]和q [j]都小,所以很显然,当q[k]没有被弹出 的时候,另外两个数也都不能被弹出 而之后,无论其它的数字在什么时候被弹出,q [j]总是会在 q [i]之前弹出.而q [j]>q [i],这显然是不正确的.

证明
? 必们要一性定:满也足就条是件,p如.这果里两我个们数来不证可明以它压的入逆同否一命个题栈,也,那就么是它" 如果不满足条件p,那么这两个数一定可以压入同一个栈.“
? 不q[i满]<q足[j条],q件[k]p>有q[两i];另种一情种况是:一对种于是任对意于i<任j,q意[ii]<>jq<[kj]且. ? 第一种情况下,很显然,在q[k]被压入栈的时候,q[i]已经被弹
出栈.那么,q[k]不会对q[j]产生任何影响(这里可能有点乱, 因还充为需分看要性起另的来一时个候,当数所q[说Rj],<满的q[足情K]J的况<K时…<R而候且事,是q实[会r]上<有q我[影j]们<响q现[的k在],,也但并就实不是际考证上虑明,这这 个r,所以说q[k]对q[j]没有影响). ? 第以这二所样种有,原情数命况字题下都的可,我逆以们否压可命入以题同发得一现证个这,所栈其以.实原就命是题一得个证降. 序序列,所 ? 此时,条件p为q[i]和q[j]不能压入同一个栈的充要条件也得 证.

构图
? 这样,我们对所有的数对(i,j)满足1<=i<j<=n,检查是 否存在i<j<k满足q[k]< q [i]<q [j].如果存在,那么在 点i和点j之间连一条无向边,表示q [i]和q[j]不能压 入同一个栈.
? 二分图的两部分看作两个栈,因为二分图的同一部 分内不会出现任何连边,也就相当于不能压入同一 个栈的所有结点都分到了两个栈中.
? 此时我们只考虑检查是否有解,所以只要O(n)检查 出这个图是不是二分图,就可以得知是否有解.

深度优先搜索求解
? 检查有解的问题已经解决.接下来的问题是,如何找到 字典序最小的解. 实际上,可以发现,如果把二分图染成1和2两种颜色,那 么结点染色为1对应当前结点被压入s1,为2对应被压入 s2.为了字典序尽量小,我们希望让编号小的结点优先 压入s1.
? 又发现二分图的不同连通分量之间的染色是互不影响 的,所以可以每次选取一个未染色的编号最小的结点, 将它染色为1并从它开始DFS染色,直到所有结点都被 染色为止.这样,我们就得到了每个结点应该压入哪个 栈中 。
? 还有一点小问题,就是如果对于数对(i,j),都去枚举检查 是否存在k,使得q[k]<q[I]<> M

最优乘车(NOI97)
? 一名旅客最近到H城旅游,他很想去S公园游玩,但 如果从他所在的饭店没有一路巴士可以直接到达S公 园,则他可能要先乘某一路巴士坐几站,再下来换乘 同一站台的另一路巴士, 这样换乘几次后到达S公园。
? 现在用整数1,2,…… N 给H城的所有的巴士站编号, 约定这名旅客所在饭店的巴士站编号为1,2,…… S, 公园巴士站的编号为N。
? 写一个程序,帮助这名旅客寻找一个最优乘车方案, 使他在从饭店乘车到S公园的过程中换车的次数最少。
? 输入N和M条公交线路信息 ? 求最少换车的次数

模型的构建

我们来分析样例 37 67 4736 2135

67

473

6

213

5

? 考察4 ——> 7 ——> 3 ——> 6这条线路。由于巴士在同一 线路上行走不需换车,我们可设4 ——> 7,4 ——> 3,4 — —> 6,7 ——> 3,7 ——> 6,3 ——> 6这些边的权值都为1。 对每条线路我们都这样构图,然后问题就转化成求起点1 到终点n的最短路。

01串问题(NOI99试题)
? 给定7个整数N,A0,B0,L0,A1,B1,L1,要求设计一个01串 S=s1s2…si…sN,满足:
(1)si=0或si=1,1<=i<=N; (2)对于S的任何连续的长度为L0的子串sjsj+1…sj+L0-1(1<=j<=N-
L0+1),0的个数大于等于A0且小于等于B0; (3)对于S的任何连续的长度为L1的子串sjsj+1…sj+L1-1(1<=j<=N-
L1+1),1的个数大于等于A1且小于等于B1; ? 例如,N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2,则存在一个满足
上述所有条件的01串S=010101。 输入: N,A0,B0,L0,A1,B1,L1(3<=N<=1000) 输出:一个满足所有条件的01串。

构图

(1) 图的节点

用Ci表示s1,s2….si中1的个数,我们可以得到C1,C2….Cn,用 他们作图的节点,将C0也考虑进去(显然:C0=0),我们 就得到了N+1个节点。

(2)图的边与权。若我们已找到一个串S,则这个串S必须 满足如下性质:对任意的i,C i一定符合下面的不等式:

?Ci ? 0 ? Ci ? 1

?Ci ? 0 ? Ci ? 1

??Ci ? 1 ? 1 ? Ci

? ?

A1

?

Ci

?

L1

?

Ci

?

B1

??Ci ? 1 ? Ci ? 1

?

??Ci ??Ci

? ?

(? B1

A1) ? Ci ? Ci ? L1

?

L1

??A0 ? L0 ? (Ci ? L0 ? Ci) ? B0

?Ci ? (L0 ? A0) ? Ci ? L0 ? ??Ci ? (B0 ? L0) ? Ci ? L0

? 样例构图 ? 输入:6 1 2 3 1 1 2 ? 输出:010101

模型求解

(1) 判断是否有解

?Ci ? x ? Cj

? 考虑下面这样一种情况:??Cj ? y ? Ck ? Ci ? (x ? y ? z) ? Ci

? 若x+y+z < 0 则 Ci < Ci

??Ck ? z ? Ci

? 这显然是不可能得到的,所以若是出现了这种情况,则说

明无解。这种情况就是构建的图中出现负权回路的情况!

(2)求出S序列

? 要求出S序列,我们只要求出C数组就可以了。因为C数组 和S序列是一一对应的关系。而C数组的值,又可以通过构 建就的是图各论个模节型点来的求值。。图由中于C有0节负点权到,各我个们节可点以的选最择短Be距llm离an,Ford算法。


更多相关标签: