集训队作业matrix解答

1、Matrix福建省福州一中李晓潇题目大意题目大意题目说明：搜索搜索万能！搜索算法优化一边搜索，一边计算时间复杂度： O（2N*N2）空间复杂度： O（N2）期望得分：2030深入分析想要得到一个高效算法，需要分析题目的特点。本题的突破口：深入分析根据矩阵乘法分配率可得：深入分析我们先对减号前面部分进行分析；a1 a2 aN-1 aNb11 b1NbN1 bNNa1 a2 aN-1 aN*将 写做矩阵的形式：=a1 a2 aN-1 aNb11 b1NbN1 bNNa1 a2 aN-1 aN*a1 a2 aN-1 aN=由于构造的A矩阵是一个01矩阵，所以上式我们也可以这样表示：深入分析我们再对减

2、号后面部分进行分析；c1 c2 cN-1 cNa1 a2 aN-1 aN*也将 写做矩阵的形式：深入分析根据以上的分析，我们可以知道：根据上式可知，对于ai=1,最后的D矩阵的元素值就要扣除ci ；当ai=1且aj=1时，最后D矩阵的元素值就可以加上bij，我们的目标是最大化D矩阵。我们发现问题中B矩阵十分类似用于描述图的邻接矩阵，因此我们联想到可以尝试用图论模型来描述这个问题。深入分析 首先，对于B矩阵的元素bij是否加入答案与ai和aj 两个元素有关，因此我们可以令其为i，j之间连边的边权；对于C矩阵的元素ci是否从答案中扣除只与ai有关，所以我们可以令其为点i的点权；那么A矩阵中ai为0

3、或1就可以表示最后方案中对i点的决策。图论模型给出一个N个点的带权无向完全图，每个点的权值为pi=ci-bii,图中点i和点j(ij)之间所连接的无向边边权为wij= bij +bji;要求你寻找一个子图，使得子图内边权之和减去点权之和最大。NOI2006 最大获利经典算法我们可以套用最大权闭合子图的算法，例如下图：312123(1,3)(1,2)(2,3)142522252-1-2-4ST252124经典算法套用了最大点权闭合子图的经典模板，我们可以构造出一个N 2个点N 2条边的网络，对于70%数据，这个算法已经可以处理。但是注意到最大数据中N达到了600，构造出来的网络中可能会有10万多

4、个点，在1s时限下，该算法明显力不从心。时间复杂度：Maxflow(N2,N2)空间复杂度： O（N2）期望得分：6070另辟蹊径 上面的算法之所以不能很好的解决问题，是由于没能抓住题目的特点，一味的套用经典模板，导致了时间效率的低下。 因此，我们需要另辟蹊径，寻找新的构图方法。另辟蹊径最大流最小割最大化最小化等于补集转换对应返回求值另辟蹊径 令原图为G=（V，E），选出的子图为 G=（V，E）, 为E的补集。最大化最大化由于 是一个定值，所以我们的目标变成了: 最小化：成功将问题转化为最小化问题。另辟蹊径将问题变成最小化问题后，我们的目标就是构建网络，使得图的割与取点方法一一对应，通过求解最

5、小割来求最小值。我们先从简单的情况开始考虑，假设图中有两个点A，B权值为pA ， pB;他们俩之间的无向边权值为wAB。网络构图 我们令最后割集中，所有i 都属于V集合， i 都不属于V集合。那么我们不难得到下图：ASBTpAwAB/2wAB/2wAB/2wAB/2pB点A和点B是否属于集合V一共有4种情况，同样，构建网络的割也共有四种情况，它们之间一一对应；ASBTpAwAB/2wAB/2wAB/2wAB/2pB此图的割：A，B都属于S集，割大小为pA+pB。对应的方案点A和点B都属于V, 。ASBTpAwAB/2wAB/2wAB/2wAB/2pB此图的割：A属于S集，B属于T集，割大小为p

6、A+wAB。对应的方案为仅点A属于V, 。ASBTpAwAB/2wAB/2wAB/2wAB/2pBASBTpAwAB/2wAB/2wAB/2wAB/2pB此图的割：A，B都属于T集，割大小为wAB。对应的方案点A和点B都不属于V, 。此图的割：A属于S集，B属于T集，割大小为pA+wAB。对应的方案为仅点A属于V, 。网络构图更一般化的，对于N个点的图，我们可以新建源汇S和T，从S向N个点连有向边，连向点i的边容量为 。从N个点向T连有向边，点i连向T的边容量为 ；图中N个点，对于任意有序点对i和j（ij），从i向j连有向边，容量为wij/2。网络构图注意到在之前的讨论中，我们默认了权值为非负

7、数，但是实际上点权为pi有可能为负数，应该如何处理呢?根据贪心的思想，我们权值为负数的点一定在最优解中。这也是很好证明的，假如最优解没有选择这个点，那么我们把这个点加入V集合， |V|的值将减小， |E|的值不会减小 ，那么最后的答案 将变得更优。网络构图这样，通过求最小割就可以求出 的最小值，即我们就可以得到最大的 ，问题得到解决。当然，即使采用了这样的方法构图，图还是很稠密的，所以，要注意网络流的优化问题，标程采用的是Sap算法+当前弧优化（在稠密图上当前弧优化往往效果很好），极限数据可以在0.5s以内出解。时间复杂度：Maxflow(N,N2)空间复杂度：O（N2）期望得分：80100思

8、路总结矩阵问题搜索时间复杂度太高图论问题经典模型网络规模太大最大化问题最小化问题最小割成功解决题目特色严谨正确题目创新题目难度严谨正确数据生成本题的数据规模较大，如果纯随机的生成矩阵B和C，往往会因为过于平均而造成矩阵A的最优解全是0，或者全是1。笔者为了避免这种情况的出现，在生成数据的时候希望矩阵元素之间的差距尽量大。对于每个格子以1/5的概率生成一个很小的随机数，以1/5的概率生成一个很大的随机数，其他情况生成一个正常随机值。 仅仅这样还是不够的，在生成数据的过程中还要考虑B，C矩阵元素值的比例与N的大小关系，随机数的范围，等等 为了保证数据足够强，及其正确性，生成数据时笔者一共写了8个不同的程序进行试验。严谨正确语言平衡性在现行的制度下，参加NOI选手可以使用Pascal，C和C+三种语言，因此出题就要考虑这三种语言的公平性，这也是很容易被忽略的。为了保证公平性，笔者特意用三种语言写了程序进行比较，发现本题的读入数据规模较大，而C和C+即使用scanf（）读入数据的速度比Pascal慢了许多，往往因为数据的读入造成劣势，对于这个问题，题目的最后特意加了个“友情提示”，给出C/C+快速读入的方法，避免因语言造成的不公平。题目创新矩阵与图论结合题目成功的用矩阵运算来包装图论问题。突破传统经典算法经典算法不能很好处理问题，需要分析问题本质，