P3965-Solution
strcmp
·
2023-03-24 22:13:05
·
题解
题目大意： 给定一个 n \times m 的字符串网格图，字符集为 \{\texttt{L},\,\texttt{R},\,\texttt{U},\,\texttt{D}\} ，分别代表若进入当前网格，则需要分别向左，右，上，下方向走一格。求出一个修改网格图中字符的方案，使得从任意初始网格出发，经过若干轮之后都会回到初始网 格，输出最小的修改次数。
Solution
一般来说这种状压很难做的小范围的网格题，往网络流的方向想是没有错的。
结论 1 ： 若将答案的网格图 中网格所指向的方向连一条有向边，建出的有向图满足所有结点的入度都为 1 。
证明：
显然，所有结点的出度都为 1 ，图中结点的出度之和为 n \times m 。
又，有向图中结点入度之和与出度之和相等，所以图中结点入度之和为 n \times m 。
考虑反证法，设存在一个结点入度大于等于 2 。则剩下 n \times m - 1 个结点的入度之和必然小于或等于 n \times m - 2 ，根据抽屉原理，必然存在一个结点入度为 0 。而从入度为 0 的结点出发，必然不存在任何进入该结点的路径，所以没有结点的入度大于等于 2 。结点入度为 0 的情况同理。
证毕。
结论 2 ：在任意合法方案中，若将任意结点所出发的回路视记录下来，这些回路两两之间必然不相交。
证明：假设存在两个回路相交，则在其中某一回路的某一结点上必然存在出边同时指向该回路的某个结点和另一个回路的某个结点，与结点出度都为 1 矛盾，所以回路之间必然两两不相交。（这点很重要）
如果您做过 P4003，这道题就是一个弱化版。
由于要同时方案的合法性和修改的最优性，考虑费用流。
为了同时描述每个结点是出流还是入流，我们选择拆点，将 u 拆为 u' 和 u'' ，分别表示当前的流是要从 u 出去还是直接从 u 进去。
每个结点都可以出发，于是建立超级源点 s ，从 s 连向所有结点 u 的入点 u' 。容量为 1 ，费用为 0 。
此时我们对每个结点的出点，直接连向超级汇点 $t$ 即可。
跑费用流，费用流即为答案。
#### 考虑为什么这样做是对的。
首先证明其**合法性。**
要证明合法性，首先有 $n,\,m \ge 2$ 时答案的**存在性**。
这本质上是网格图的多重回路覆盖问题计数，可以直接构造，略。
证明了存在性，则若要使得最大流最大，每个结点必然出去了一个流，进入了一个流，使得总和为 $n \times m$，按照流的方向构造方案。这点可以直接构造一个多重回路覆盖然后将环上的结点的流强制导向下一个结点，最大流已经是 $n \times m$ 了，该方案的合法性是显然的。
接下来证明其**最优性**，假设存在方案使得最小费用不优，则直接按照该方案，在环上将每个结点导向环上下一个结点的出点。该流是合法的，与最小费用矛盾。所以最小费用流的费用即为最优方案的答案。
参考代码：（远古代码，请见谅）
```cpp
#include <bits/stdc++.h>
using namespace std;
#define inf 1000000000000000
#define V 100100
#define E 500100
typedef long long int ll;
struct edge {
int to, next;
ll capa, cost;
};
int cnt = 0, head[V], n, m; edge node[E];
inline void add(int fir, int nxt, ll w, ll c) {
node[cnt].to = nxt,
node[cnt].capa = w,
node[cnt].cost = c,
node[cnt].next = head[fir],
head[fir] = cnt++;
}
int s, t, cur[V]; deque<int>que; ll dep[V], sum = 0, cost = 0;
bool vis[V];
inline bool spfa() {
for (register int i = 1; i <= t; ++i)dep[i] = inf;
dep[s] = 0; que.push_back(s); int u, v;
while (!que.empty()) {
v = que.front(); que.pop_front();
for (register int i = head[v]; i != -1; i = node[i].next) {
u = node[i].to;
if (dep[v] + node[i].cost < dep[u] && node[i].capa) {
dep[u] = dep[v] + node[i].cost;
if (!que.empty() && dep[u] < dep[que.front()])que.push_front(u);
else que.push_back(u);
}
}
}
return (dep[t] != inf);
}
ll dfs(register int v, register ll flow) {
if (flow == 0 || v == t)return flow; ll used = 0, wei = 0;
vis[v] = true;
for (register int i = cur[v]; i != -1; i = node[i].next) {
cur[v] = i;
if (!vis[node[i].to] && dep[node[i].to] == dep[v] + node[i].cost && node[i].capa) {
wei = dfs(node[i].to, min(flow - used, node[i].capa));
if (wei) {
node[i].capa -= wei,
node[i ^ 1].capa += wei,
used += wei,
cost += node[i].cost * wei;
}
}
if (used == flow)break;
}
vis[v] = false;
return used;
}
inline void Dinic() {
while (spfa()) {
memcpy(cur, head, (t + 1) * sizeof(int));
sum += dfs(s, inf);
}
}
inline void addE(int u, int v, ll w, ll c) {
add(u, v, w, c);
add(v, u, 0, -c);
}
inline int iid(int x, int y) {
return (x - 1) * m + y;
}
inline int oid(int x, int y) {
return iid(x, y) + n * m;
}
int mtx[205][205]; char c;
int dx[5] = { 0, 1, 0 ,-1, 0 }, dy[5] = { 0, 0, 1, 0, -1 };
int main() {
ios::sync_with_stdio(0);
cin.tie(); cout.tie();
memset(head, -1, V * sizeof(int));
cin >> n >> m; s = 2 * n * m + 1, t = 2 * n * m + 2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
if (c == 'D')mtx[i][j] = 1;
else if (c == 'R')mtx[i][j] = 2;
else if (c == 'U')mtx[i][j] = 3;
else mtx[i][j] = 4;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
addE(s, iid(i, j), 1, 0);
addE(oid(i, j), t, 1, 0);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 1; k <= 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (nx == 0)nx = n;
else if (nx == n + 1)nx = 1;
if (ny == 0)ny = m;
else if (ny == m + 1)ny = 1;
if (k != mtx[i][j])addE(iid(i, j), oid(nx, ny), 1, 1);
else addE(iid(i, j), oid(nx, ny), 1, 0);
}
}
}
Dinic();
cout << cost << "\n";
return 0;
}
```