讲义集训队作业-matrix

1、Matrix 解题报Matrix 解题报李晓高三五1题目大问题分题目大问题分算法算法算法算法思路总参考文感附知识2题目大N*N B bi j 1*N题目大N*N B bi j 1*N 的非负矩阵C ci j 。Aai j 一个1*N 0，1 Dd A*BC)*ATi D1*1 ADD问题分算法在乍看之下没有很好想法的情况下，搜索往往就成为一种万能的解法。看到题目 N 20A 重新计算A*BC)*AT2N*N2N 20N 5011011 A A*B的值。令矩阵E A*B，搜索过程为代码如下：if (i N ) ansmax(ans,(EC)*AT3aiSEARCHaifor j1 to ejej

2、aiSEARCHaifor j1 to ejejbiSEARCHj to ejejbi30%时间复杂度O(2NN2O(N2空间复杂度期望得分2030 算法DD (A*BC)*D A*B*AT C*= ) 124 2= = 2= = =1 A0，1 =1 =1 = c)12=A0，1 = =1 =1 = =1 =1 5 a ai 1aj 1bi j 就会加入最后的答案。我们发现B B矩阵的元素bij aiaji，jC 矩阵的元素ci ai iAai01iNpi ci bii ,ij(ij)wi j bi j bji NOI2006 NN 6S，TS T 2006 S，TS T 2006 1797

3、00 个，1s 时间复杂度 O(Maxflow(n2n2O(N26070 10 N 个点的无向完全图，点ijwi j bi j bji ，点ipi c1i bii 7令原图为 G VE) ， 我们最后选择的子图为 GV E) V V 的补集：V V V EEE EE|令原图为 G VE) ， 我们最后选择的子图为 GV E) V V 的补集：V V V EEE EE|E V E集合和V | | EE V E V N 2AB pApB E V 4 E V 4 S 集合的点属于V ，在割中属于T 集合的点属于V 择方法刚好就与图的四种割联系起来（红色的边为割边81AV BV ，此时E V W ，对

4、应的割如图，割大小也为W W pA ，对应的割如图，割大小也为1AV BV ，此时E V W ，对应的割如图，割大小也为W W pA ，对应的割如图，割大小也为W pA2AV BV ，此时E V W pB ，对应的割如图，割大小也为W pB3AV BV ，此时E V 4. AV BV ，此时 pA pB pA pBE V 9N S ，汇T S N 各连一条有向边，与第i个点连边的容量为 N 个点各向汇T 连一条有向边，第i2p N 之间相互连边，对于i, j 两个点(i jwi j i2定理：图的割与VN S ，汇T S N 各连一条有向边，与第i个点连边的容量为 N 个点各向汇T 连一条有向

5、边，第i2p N 之间相互连边，对于i, j 两个点(i jwi j i2定理：图的割与V 和V E V S集合的点在划分时属于V 集合，割中属于T 属于V 集合，那么我们就做到割与V 和V 的划分一一对应，此时割的大小为 + 22=1 =1 = + 222=1 =1 =1 = 2=1 =1 = 2=1 =1 =+ =1 =1 E V 根据以上定理， 最小割对应着就是最小的，这样我们就能得到最大的E V ) DEpi c1,i bii V。我们可以用反证法来证明：假设在某个最优解中，这个负权点不在V ( E V ) E V 根据以上定理， 最小割对应着就是最小的，这样我们就能得到最大的E V

6、) DEpi c1,i bii V。我们可以用反证法来证明：假设在某个最优解中，这个负权点不在V ( E V ) 点放入V E V E 0) sap+0.5s 时间复杂度 O(Maxflow(nn2O(N2空间复杂度期望得分80100 算法 = =1 = =1 = =1 =1 =1 = + =1 =1 因为 是一个定值，所以我们将问题转化成一个最小化问题，目标最 法是相同的S 汇T N S N 个点各连一条有向边，向iNbji N (i, j)(i jij的边的容量为bi j jN 个点向汇T i点连出去的边的容量为ci 这样我们可以将图的割与+ + 的值一一对=1 D时间复杂度 O(Maxflow(nn2O(N2空间