2010-图基本算法2.ppt

给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。 增广路的定义(也称增广轨或交错轨)： 若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。 由增广路的定义可以推出下述三个结论： 1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。 2－P经过取反操作可以得到一个更大的匹配M’。 3－M为G的最大匹配当且仅当不存在相对于M的增广路径。 用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出) 算法轮廓： (1)置M为空 (2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M (3)重复(2)操作直到找不出增广路径为止 int sum =0; memset(match,-1,sizeof(match)); for (int i=1; i=N; i++) { memset(vis,0,sizeof(vis)); if (dfs(i)) sum++; } …… …… …… …… bool dfs(int u) { for(int v=1;v=N;v++) if(mat[u][v]!vis[v]) { vis[v]=true; if( match[v] ==-1 ||dfs(match[v] )) { match[v]=u; return true; } } return false; } 每个点寻找增广 ：邻接 ：询问 ：匹配 2012来临之际，世界正在遭受着各种灾难。 深远领主 丁丁二世也在这时候显露了他邪恶的本性。 丁丁拥有制造地震和海啸的能力。 这一次，丁丁决定用最多的“超级组合”来破坏ACM实验室的稳定与和平。 丁丁能制造 n 个地震， m 个海啸。 每个地震对于海啸都有着特殊的喜好，只有地震 和其 喜好的海啸联手，才能成为一个超级组合。 请聪明的ACMer你算出每次丁丁最多能派遣多少个“超级组合”，好让我们共同抵御丁丁的“超级组合”！ 定义：在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联 定理：最小路径覆盖＝｜Ｐ｜－最大匹配数 小怪兽们又来袭击地球了！英勇的凹凸曼在危急时刻赶了过来，这时小怪兽们正好聚集在一块平地上，我们把平地划分为N行M列，每个小怪兽恰好在一个格子里。凹凸曼观察后得出了小怪兽们的具体位置。凹凸曼打算用奥术光波干掉这些小怪兽，已知奥术光波每发可以干掉一行或者一列的小怪兽。请问凹凸曼至少要几发奥术光波才能消灭所有的小怪兽？ 最小点覆盖问题，把行和列作为两个集合，怪兽作为边！ POJ 3041 一个新的问题 老师要带学生们出去远行，但是这个保守的老师不希望男女生们在旅行途中恋爱，所以他要使得谈恋爱的可能性尽量小，并且带出去最多的学生。  ?he has made some rules that he thinks indicates a low probability two persons will become a couple:?Their height differs by more than 40 cm.? They are of the same sex.? Their preferred music style is different.? Their favourite sport is the same So, for any two persons that he brings on the excursion, they must satisfy at least one of the requirements above. Help him find the maximum number of persons he can take, given their vital information. 设G=(v,e)是n阶图，