昨天晚上做了清北学堂的比赛“首届信息学在线测评大赛Q1”，名字很响亮。今天写了一份题解，发出来。
第一题:低价购买
要求求出方案数的最长单调序列(LIS)问题。我把序列先...
|
|||||
|
[二分图带权匹配与最佳匹配] 什么是二分图的带权匹配？二分图的带权匹配就是求出一个匹配集合，使得集合中边的权值之和最大或最小。而二分图的最佳匹配则一定为完备匹配，在此... 把每个政党的两个议员看作两个顶点，不能相处的议员之间连接一条边。类似于二分图的染色，但又不是严格的二分图。我们规定第2*i-1和2*i个顶 点为姊妹顶点。对于图中的每个连通分量，... 这道题的错误做法很多,但是实际在考场上，大多数人拿到了30分。错误做法却能得满分的也很多,正确的算法是基于二分图的算法。注意，不是二分图匹配！ 分析条件，我们把问题抽象... 匈牙利算法 链接： 这是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出，因而得名。 ...
|
|
||||
|
Copyright © 2010 Beyond the Void - All Rights Reserved
|
|||||