[SGU121 Bridges painting]【构造法】

【题目大意】

给定一个无向图，把每条边黑白染色，使得所有的度大于等于2的点有至少有一条黑边和一条白边相连。

【算法分析】

很久之前写过随机算法过了，现在贴一个构造法的。

其实主要是update函数非常精髓。

首先构建dfs树，无向图dfs树具有的一大优点是该点只会向自己的祖先或子孙有非树边。

然后按深度交替染色。返祖边与自己的儿子涂同样的颜色。

如果dfs树中根结点度超过1，那么就找一条边染不同的颜色。

否则看根结点是否满足条件，如果不是，那么找一个与根结点相连的叶子，向上找到一个度大于2的点为止，将该路径上所以边反色，并且将根与该叶子的边反色。如果找不到度大于2的点，那么是奇环，无解。

【CODE】

C++ CODE   :SGU121 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99100101 #include

NOIP2010提高组解题报告——Flow

【题目大意】

给定一个N*M(N,M<=500)的矩阵，矩阵中每一个格子都有一个权值。

1、只有第一行的格子能够建蓄水厂。

2、若与该格子有公共边的格子已经建有水利设施，并且这个建有水利设施的格子的权值大于该格子的权值，那么该格子可以建一个输水站。

问：能否使最后一行所有的点都建上水利设施？若能，则输出最少建多少个蓄水厂可以达到要求。若不能，则输出最后一行有多少个格子无法建立水利设施。

【算法分析】

首先注意到两个性质。

1、假设i,j都为第一行建蓄水厂的位置，那么他们供给最后一行的水利设施的配对关系可以不交叉。

如图：

若交叉，那么i必然能控制j现在控制的点。于是反证得该性质正确。

2、假设最后一行的每个点都能被覆盖，那么对于第一行的每一个结点，它所能控制最后一行的位置必然是连续的。

如图：

若不连续，根据性质1可知，其它点也无法覆盖红色部分，于是与“有解”这一前提矛盾，反证得该性质正确。

得出这两个性质以后解法就呼之欲出了。

首先把所有第一行的结点放入队列之中，进行广度优先搜索，然后可以看最后一行有多少个点被扩展到，从而得出是否有解以及有多少个点无法被覆盖到。

下面处理有解的情况。

对于每一个点，建立两个项L[i][j],R[i][j]，表示从这个点流出去，能覆盖到最后一行的最左端点及最右端点。

那么怎么快速处理得出所有点的L[i][j]及R[i][j]呢？

我们初始化所有L[N][i]=i , R[N][i]=i。

然后扩展开去影响其他的点。

笔者认为扩展有两类比较好的方法：

1、这个过程比较类似于最短路的扩展，所以SPFA或者Dijkstra+Heap都是不错的选择。使用它们的时间复杂度分别是O(kNM)、O(NM lg NM)

2、这个图显然是有向无环图，我们可以对它拓扑排序，然后按拓扑序扩展。这样做的时间复杂度O(NM)。或者说更直接一点按所有点的权值排序，然后按权值从小到大的顺序扩展。这样做的时间复杂度是O(NM lg NM)。

处理出所有的L[i][j]以及R[i][j]以后，问题就转化为：用最少的第一行的区间覆盖[1,M]这段所有的点。

令L’[i]=L[1][i]，R’[i]=R[1][i]。

我们按L’[i]把第一行的区间排序以后，就可以使用一个简单的贪心算法在O(M)的复杂度内解决这个问题。

这个贪心的C++代码如下，其中Q[i].L等价于L’[i],Q[i].R等价于R’[i]：

               int MaxR=0,ans=0,tmp;

               i=1;

               while (MaxR

                     tmp=MaxR;

                     while (i<=m && Q[i].L<=MaxR+1)

                       tmp=max(tmp,Q[i++].R);

                     MaxR=tmp;

                     ans++;

               }

               printf("%dn",ans);

【复杂度分析】

综上，我们如果在扩展时使用拓扑排序，那么可以做到

O(NM+M lg M)的时间复杂度 (这已经和读入数据所必须耗费的时间差不多了)

O(NM       )的空间复杂度

NOIP2010提高组解题报告——Prison

【题目大意】

给定一个无向图。

我们用三个值来描述一条边：Edge.w(该边的权值),Edge.x,Edge.y(该边所相连的两个顶点)。

现需要把该图里的点分在两个集合A,B中。

令Weight_A=Max(Edge.w | Edge.x∈A，Edge.y∈A)

令Weight_B=Max(Edge.w | Edge.x∈B, Edge.y∈B)

则Answer=Max(Weight_A,Weight_B)

问Answer最小能是多少？

【算法分析】

本题有两种思路。

【算法一】

先二分答案，然后单独地判定可行性。

注意到二分答案Limit以后，使用所有Edge.w>Limit的边构成一个新图。然后这个可行性问题可以转化为：判定该新图是否一个二分图。

对于这个问题，我们可以通过对每个点黑白染色来判定。

染色过程如下：

使用广度优先搜索或者深度优先搜索遍历全图，对于一个连通分量，先对其中一个点染上白色。然后再将与它相邻的点都染成和该点相反的颜色。如此下去，不同连通分量分别处理，最后得到一个所有顶点都经过染色的图。然后检测是否存在一条边所连接的两个顶点颜色相同，若是，则不可行，否则可行。

【时间复杂度】O(V lg 10^9+E lg 10^9)

【空间复杂度】O(V+E)

【算法二】

注意到答案一定是某条边的权值，那么我们把边按权值从大到小排序，然后枚举答案，并考虑答案的改变，情况会发生什么变化。

答案每次减少一点，就会加入几条边，我们现在要在线判定新加边以后，该图是否还是二分图。那么我们用并查集维护每个连通分量，利用该点到并查集中根的距离判定染白色还是黑色。然后如果新加入一条边，连接同一连通块的两点并且他们到根的奇偶性相同，那么出现矛盾，不可行。否则，合并两个集合。

【时间复杂度】O(E lg E + V α(V))

【空间复杂度】O(V+E)

NOIP2010提高组解题报告——Tortoise

【题目大意】

给定N(1<=N<=350)个排在一行的格子，每个格子上都有一个权值。同时给出M(1<=M<=120)张卡片，每张卡片上有[1,4]中的一个数字。一开始游戏者站在第一个格子处，每使用一张写着数字x的卡片，那么向后跳x步，并得到该格子上的权值。卡片不可重复使用。数据保证每种卡片的数量不超过40，并且所有卡片上的数字之和与N-1相等。

【算法分析】

本题很容易使用动态规划解决，而且可以通过所有数据的状态定义也有很多种。由于转移都比较简单，并且几乎都一样思路，所以转移方程在此略去。

【算法一】

F[i][j][k][l]表示写着数字1、2、3、4的卡片分别剩下i、j、k、l张时的最大得分。

(可以使用n-(i*1+j*2+k*3+l*4)来得知当前到达哪一个格子)

【时间复杂度】

O(41^4+N+M)

【空间复杂度】

O(41^4+N+M)

【算法二】

F[i][j][k][l]表示跳到了第i个格子，写着数字2、3、4的卡片分别剩下j、k、l张时的最大得分。

(可以使用n-i-j*2-k*3-l*4来得知1号牌剩下多少张)

【时间复杂度】

O(N*41^3+N+M)

【空间复杂度】

O(N*41^3+N+M)

【算法三】

F[i][j][k][l]表示剩下i张牌可用，写着数字2、3、4的卡片分别剩下j、k、l张时的最大得分。

(可以使用i-j-k-l得知1号牌剩下多少张)

【时间复杂度】

O(M*41^3+N+M)

【空间复杂度】

O(M*41^3+N+M)

NOIP2010提高组解题报告——Translate

【题目大意】

给定一个有M(0

【算法分析】

由于数据范围很小，做法很多，这里只介绍一种较优秀的算法。

首先建立一个哈希表和一个队列。

哈希表用来判断该元素是否存在于储存器中。

而队列的先进先出的性质与题目要求刚好相符合。

对于每次输入，先在哈希表中查找，如果存在，那么什么也不用做，否则插入队列，如果队列超过了规定的长度，那么把队头元素出队即可。

【时间复杂度】

O(M+N+Max(a[i]))

【空间复杂度】

O(M+N+Max(a[i]))