【题目大意】
给一个弦图。问色数是多少。
【算法】
先是有显然的定理：色数(用最少种颜色涂满图中的点，使得每条边两端的点颜色都不同)>=团数(最大团的点数)
因为是弦图，由完美消除序列的性质可以构造得色数=团数，于是达到下界。
于是直接利用完美消除序列的性质求出团数即可。
【其它】
完美消除序列的性质是：
对于序列中第i个点Vi。
令S={Vj | (j>i) && ((Vi,Vj) in E)}，那么S+Vi成一个团。
>.<还是V^2。虽然O(V+E)也不难写。求不鄙视。
【CODE】
标签存档：图论
World Final 2006 Problem J —— Routing
【提交地址】http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=16007
【题目大意】
给定一个有向图G(V,E),|V|<=100,然后边数可以接近完全图。
求一个包含点数最少的强连通分量，并要求这个强连通分量包含点1和点2。
【算法分析】
一开始我和叉姐一致认为，答案应该是这样的(其中有【可怜图】标记的边代表一条包含若干点的路径)：
但是实际上，围观这样一个图，它也可能是答案：
也就是说答案应当由数个环拼接而成的，但是这些环不一定只交于一个点，而有可能交在一条链上。
下面来感性地认识一下。图中的3个环用红圈标起来了。
被【可怜图】所代表的路径其实都是酱油的。关键在于环和环的交接处，也就是图中的每一列上面的链。（一个点也可以看作链）
很容易发现，如果要往后并入环，那么只需要交界处的信息的就可以了。
比如说已经处理了图中的第一个环以后，如果要并入第二个环，我们需要的信息就只有8 -> 3 -> 4这条链。实际上3都不需要了，只要知道这是一条从8出发，到达4的链。然后对于另外一条链，如果要并入这个环，只需要接在8和4上就够了。
所以本质上来说，带【可怜图】的边，以及每一列的链上中间的过程都不重要，所以这些部分可以直接用最短路径代替。
处理时可以建一个数组ins[i][j]，表示从i到j的路径上至少需要多少个点(这个很容易用Floyd实现)，然后直接拼接就可以了。
于是很自然地想到定义状态d[i,j]表示最后以i->j的最短链作为和下一个环的公共部分，并且i->j这条最短链已经并入1点所在的环时最少需要多少个点。然后就是各条链之间转移了。由于每次转移，包含的点必然不减，也就相当于最短路中没有负权边，所以可以利用朴素的dijkstra算法求解。
最终时间复杂度O(n^4) （一共有n^2条最短链，它们之间可能有接近完全图的边）
跑了2730MS……
求更好的算法。
【CODE】http://ideone.com/9uxRj
[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提高组解题报告——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)
[HDOJ3666 Regional Harbin THE MATRIX PROBLEM]【差分约束系统变形】
【题目大意】
给定一个矩阵C[i][j]，每行数都乘一个a[i]，每列数都除以一个b[i]，然后使得矩阵里每个数都L<=x<=U。
问是否存在这样的a[i],b[i]。
【算法分析】
易得不等式
(a[i]/b[i])*C[i][j]>=L
(a[i]/b[i])*C[i][j]<=U
移项
a[i]*(C[i][j]/L)>=b[i]
b[i]*(U/C[i][j])>=a[i]
那么我们建边
【其它】
由于顺序问题。。。我把入栈限制限为2居然过了。。。
【CODE】
http://xiudaima.appspot.com/code/detail/1615006