前言

图论专题结束！数据库课设也只剩下小修小补，GJ！总结这次专题：见多识广，建多识广。抓紧在暑假前搞定那本书！

A. Euler

题意

判断一幅图，如果是无向图是否存在欧拉通路，如果是有向图，是否存在欧拉通路

分析

  1. 无向图：G 为连通图，并且 G 仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。
  2. 有向图：D 为有向图， D 的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为 1，另一个顶点的出度与入度之差为-1。

思考

  1. 坑点： 对于孤立点，教材说法不一，导致歧义。
  2. 技巧： 记住判断方法。

B. -0你电脑炸啦

题意

任务窗口只会在给定的位置出现，需要做的就是判定当前图像是否合法。

分析

  1. 图中需要我们找矛盾！
  2. 如果A窗口被B窗口覆盖，那么就连一条边A->B，如果B窗口又被A窗口覆盖，那么连一条边B->A。建完图后，判断是否有环即可判断是否存在矛盾。

思考

  1. 坑点： 没有吧，可能原题卡暴力了，然而我没卡= =让大家错失了一次锻炼自己思维的机会啊，23333
  2. 技巧： 建图建图，建多识广。

C. 寻找fly真迹

题意

构造一个字符串，使得把它的每个字符抽象成点，相邻字符连边能构成题目所给出的图。

分析

  1. 注意只有a,b,c三个字符！b字符和任何字符都相连！
  2. 于是，b肯定是度数为n - 1的点。剩下的就是a和c怎么安排了，从点1开始，如果没有被赋予字符就赋予字符a，然后dfs把和a以及任何a所能到的没有赋值的字符赋值为a，因为a能够相邻的只有a和b。完毕后还有字符，那么就赋值c，过程同上。（二分图染色的感觉，最后用构造出来的串比对原图即可）

思考

  1. 坑点： 很机智啊。
  2. 技巧： 就看你机智不机智了。

D. 一食堂 or 二食堂， it's a question

题意

求任意两个人到食堂的距离加上他们两人所在食堂距离之差的和的最大值的最小值。他们间有喜欢/讨厌的关系，使得要/不要在一个食堂用餐。

分析

  1. 最大值的最小值，二分既视感。
  2. 知道了答案有什么用呢？可以制造矛盾了。我们定义disA、disB分别为A、B两位同学各自到某个食堂的距离，disAB为两者所在食堂距离，如果disA + disB + disAB > 答案,那么显然这是不可行方案，所以可以推出：A去自己当前选择的这个食堂，B必须去B自己当前选择的另一个；或者B去自己当前选择的这个食堂，A必须去A自己当前选择的另一个；这里只是依据矛盾推出一些东西而已。然后再根据互相喜欢的人建立矛盾，互相讨厌的人建立矛盾。用tarjan判断矛盾是否在一个连通分量内即可。这就是所谓的2-SAT。

思考

  1. 坑点： 啊啊啊，我WA 10 发，简直啊！！！对出题人深深地唾弃= =不管怎样，反正他缩点写错了无误，TAT。
  2. 技巧： 找出矛盾，建边，判断连通分量。

E. Division

题意

不可重点的最小路径覆盖。

分析

  1. 缩点，然后二分图匹配。
  2. 二分图中，最小路径覆盖 = 点个数 - 最大匹配数

思考

  1. 坑点： 没有。
  2. 技巧： 见多识广。

F. meixiuxiu学图论

题意

找图中环上边权最大值的最小值。

分析

  1. 啊，我各种缩点，各种GG。
  2. 正解：先最小生成树，标记树上的边。然后不断添加未标记的边，显然，每加入的边必定都会构成环，而由于是最小生成树，所以新加的边一定是环上的最大值，所以拿答案和新加的边不断比较即可。

思考

  1. 坑点： 没有。
  2. 技巧： 啊，太美妙了~

G. 最短路

题意

统计图中不重边的最短路个数。

分析

  1. 不重边呀，所以说每条路径的贡献就是1咯，流啊流啊流的感觉~
  2. 想当初第一次做真是一脸蒙蔽啊= =。正解：跑最短路，把所有最短路的边留下来，然后在新图中最大流即可。

思考

  1. 坑点： 没有。
  2. 技巧： 建多识广。

H. NightMare2

题意

在不爆炸的前提下拿最多的宝藏。

分析

  1. 二话没说，感觉可能是先跑最短路，然后根据最短路答案调整的题。写完发现不对，最短路得到的宝藏数和答案没啥关系啊= =然后苦思，结果见2。
  2. 突然问自己，能不能二分？然后就出结果了= =。其实换句话说，就是在规定时间内，从起点到终点最可能经过的最小上限的路能多大？
  3. 二分宝藏价值，然后跑最短路。

思考

  1. 坑点： 没有。
  2. 技巧： 转换思维。

I. 玛雅，好简单

题意

输出一张无向图中的桥边的数目。

分析

  1. 题目太直白了，上tarjan。诶，答案怎么老是不对。啊！按点标记有问题啊TAT，怎么办！怎么办！
  2. “诶，郭**，你看看我这错哪了？”xf如是问我。“诶，你怎么标记边啊。”，对哦，标记边啊！

思考

  1. 坑点： 没有。
  2. 技巧： 转换思维。

J. An Easy Problem

题意

可重复点的最小路径覆盖。

分析

  1. 和E题很像有木有，像归像，然而还是有区别。
  2. 其它和D题一样，不过建立二分图的时候要传递闭包。

思考

  1. 坑点： 无。
  2. 技巧： 见多识广。

K. 投票

题意

每个人都能给他所能直接或者间接相连的人投一票，问：得票最多的人是几号人物？如果有多个，就按升序输出他们的号码。

分析

  1. 缩点得到DAG。得到新图。然后新图中每个点向所有直接或者间接连的点投票，票数为连通块内点个数。最终得票数就是：从其它人那边得到的票数 + 自身连通块内得到票数

思考

  1. 坑点： 无。
  2. 技巧： 缩点 + 大胆。
  3. 良心话： 缩点之后，最坏情况O(n^2/2)，就是一条链的情况。所以这种解法理论上还是会T的，好奇正解是啥。

L. Cruel War II

题意

能否用不超过10个的点覆盖完整幅图的所有路径。

分析

  1. 哦~我百度了一发一般图的最小点集覆盖，找到了一篇论文，实现了它，然后被自己一个五个点的样例叉掉！咦，原来是n^2求近似解啊！！！
  2. fly说搜索，按边搜，意淫半天，终于过了。
  3. 具体就是dfs(p, use)代表到边p，标记了use个点，如果这条边的任意一个点被覆盖了，就继续dfs(p + 1, use)，否则枚举两个点的选与不选。

思考

  1. 坑点： 让人以为是NP难题啊！
  2. 技巧： 读题 + 思考。

M. interesting

题意

大概就是问无数个a1~an能构成多少个Bmin到Bmax中的数？

分析

  1. 我的做法是对这几个数从小到大排序，取最小的非0的数，那么所有能构成的数都能分解成：0+k×ami,1+k×ami,...,ami−1+k×ami0 + k \times ami, 1 + k \times ami, ... , ami - 1 + k \times ami。然后只需要求出每个剩余结果的最小的那个值是多少就行啦。比如样例，0的最小是0，1的最小是10，2的最小是5。
  2. 然而我WA了= =

思考

  1. 。。。。。。。。。。

具体代码点击下方传送门:)

传送门

广告时间

Java学习网站: how2j

VPS: VPS