2020-2021:teams:die_java:weeksummary12

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:die_java:weeksummary12 [2020/08/28 17:13]
wxg [王兴罡]
+++ 2020-2021:teams:die_java:weeksummary12 [2020/08/28 21:18] (当前版本)
mychael
@@ 行 36: / 行 36: @@
 **hxm:**
-\\ **题目大意：**
+\\ **题目大意：** 给了一个$n*m$的棋盘的初态和终态，每次可以交换相邻两个棋子，每对位置之间交换次数有一个上限，求最小交换次数使得初态变为终态
-\\ **tag:**
+\\ **tag:** 费用流
-\\ **做法:**
+\\ **做法:** 容易想到由$S$向初始的黑点连边，由终态的黑点向$T$连边，然后相邻的点间连边
+但是这样满足不了交换次数的限制，也无法计算答案
-\\ **comment:**
+考虑如何满足一个点的交换次数限制
+当然是拆点
+但是一个位置被经过时会被交换两次，而终点和起点都只交换了一次
+那么我们就拆成三个点$left$，$mid$，$right$，分别管理入，中介，出
+它们之间顺次两边，费用为$1$
+流量将限制$lim$拆开，当$lim$为奇数时要考虑给哪一边：
+如果该点一开始是黑点，终态是白点，那么这个点出边一定比入边多
+如果一开始是白点，终态是黑点，那么一定要入边多一点
+否则一样多
+有一些要注意的地方：
+①要判黑白起始是否相同
+②相邻不止是四个方向
+\\ **comment:** 费用流模型的建立
 ----
@@ 行 58: / 行 73: @@
 ====== 黄旭民 ======
+小学期
-\\
+\\ 将所有模板整理到一个文档中

2020-2021/teams/die_java/weeksummary12.1598606018.txt.gz · 最后更改: 2020/08/28 17:13 由 wxg