描述 Description
一个循环格就是一个矩阵，其中所有元素为箭头，指向相邻四个格子。每个元素有一个坐标（行，列），其中左上角元素坐标为（0,0）。给定一个起始位置（r，c），你可以沿着箭头防线在格子间行走。即如果（r,c）是一个左箭头，那么走到（r，c-1）; 如果是右箭头那么走到（r，c+1）；如果是上箭头那么走到（r-1，c）；如果是下箭头那么走到（r+1，c）；每一行和每一列都是循环的，即如果走出边界，你会出现在另一侧。
一个完美的循环格是这样定义的：对于任意一个起始位置，你都可以 i 沿着箭头最终回到起始位置。如果一个循环格不满足完美，你可以随意修改任意一个元素的箭头直到完美。给定一个循环格，你需要计算最少需要修改多少个元素使其完美。
输入格式 InputFormat
第一行两个整数 R，C。表示行和列，接下来 R 行，每行 C 个字符 LRUD，表示左右上下。
输出格式 OutputFormat
一个整数，表示最少需要修改多少个元素使得给定的循环格完美
样例输入 SampleInput
3 4
RRRD
URLL
LRRR
样例输出 SampleOutput
2
构成一个循环即每个格子出度入度都相等为一，所以每个格子拆成入点和出点，源向入点建边容量一费用零，出点向汇点建边容量一费用零，然后相邻格子建边容量一费用为是否需要改符号。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int inf = 0x7fffffff / 27.11;
const int maxn = 20 * 20;
const int maxm = maxn * 10;
const int dx[5] = {0, 0, 0, 1, -1};
const int dy[5] = {0, 1, -1, 0, 0};
int i, j, t, n, m, l, r, k, z, y, x;
struct edge
{
int to, fl, co, nx;
} e[maxm];
int head[maxn], dis[maxn], used[maxn], pre[maxn];
int cnt, num, c;
char ch[20];
deque <int> q;
inline void ins(int u, int v, int f, int c)
{
e[cnt] = (edge)
{
v, f, c, head[u]
}; head[u] = cnt++;
e[cnt] = (edge)
{
u, 0, -c, head[v]
}; head[v] = cnt++;
}
inline bool spfa(int s, int t, int tim)
{
int i, u, v, w;
while (!q.empty()) q.pop_front();
for (i = s; i <= t; i++) dis[i] = inf;
dis[s] = 0; used[s] = tim; pre[s] = -1;
q.push_back(s);
while (!q.empty())
{
u = q.front(); q.pop_front(); used[u] = 0;
for (i = head[u]; i != -1; i = e[i].nx)
{
v = e[i].to; w = e[i].co;
if (dis[v] > dis[u] + w && e[i].fl > 0)
{
dis[v] = dis[u] + w;
pre[v] = i;
if (used[v] != tim)
{
used[v] = tim;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return (dis[t] != inf);
}
inline void mcmf(int s, int t)
{
int i, f, ans = 0;
while (spfa(s, t, ++num))
{
for (f = inf, i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) f = min(f, e[i].fl);
ans += f * dis[t];
for (i = pre[t]; i != -1; i = pre[e[i ^ 1].to]) e[i].fl -= f, e[i ^ 1].fl += f;
}
printf("%d\n", ans);
}
int main()
{
cnt = num = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &r, &c);
t = r * c;
for (i = 1; i <= r; i++)
{
scanf("%s", ch + 1);
for (j = 1; j <= c; j++)
{
ins(0, (i - 1)*c + j, 1, 0);
ins(t + (i - 1)*c + j, 2 * t + 1, 1, 0);
for (k = 1; k <= 4; k++)
{
x = i + dx[k]; if (x > r) x = 1; if (x < 1) x = r;
y = j + dy[k]; if (y > c) y = 1; if (y < 1) y = c;
if (k == 1) ins((i - 1)*c + j, t + (x - 1)*c + y, 1, (ch[j] == 'R') ? 0 : 1);
if (k == 2) ins((i - 1)*c + j, t + (x - 1)*c + y, 1, (ch[j] == 'L') ? 0 : 1);
if (k == 3) ins((i - 1)*c + j, t + (x - 1)*c + y, 1, (ch[j] == 'D') ? 0 : 1);
if (k == 4) ins((i - 1)*c + j, t + (x - 1)*c + y, 1, (ch[j] == 'U') ? 0 : 1);
}
}
}
mcmf(0, 2 * t + 1);
return 0;
}