Description
一个循环格就是一个矩阵，其中所有元素为箭头，指向相邻四个格子。每个元素有一个坐标（行，列），其中左上角元素坐标为（0,0）。给定一个起始位置（r，c）
，你可以沿着箭头防线在格子间行走。即如果（r,c）是一个左箭头，那么走到（r，c-1）;如果是右箭头那么走到（r，c+1）；如果是上箭头那么走到（r-1，c）；如果是下箭头那么走到（r+1，c）；每一行和每一列都是循环的，即如果走出边界，你会出现在另一侧。
一个完美的循环格是这样定义的：对于任意一个起始位置，你都可以i沿着箭头最终回到起始位置。如果一个循环格不满足完美，你可以随意修改任意一个元素的箭头直到完美。给定一个循环格，你需要计算最少需要修改多少个元素使其完美。
Input
第一行两个整数R，C。表示行和列，接下来R行，每行C个字符LRUD，表示左右上下。
Output
一个整数，表示最少需要修改多少个元素使得给定的循环格完美
Sample Input
3 4
RRRD
URLL
LRRR
RRRD
URLL
LRRR
Sample Output
2
HINT
1<=R,L<=15
原题题意即为将图转化成每个点入度出度恰好为1
拆点，拆成入点和出点
向本来指向的边连费用为0的边
向周围的边连费用为1的边
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#define id(x,y) (x-1)*m+y
#define N (10000+10)
#define M (1000000+10)
using namespace std;
bool used[N];
int n,m,s,e,z,Ans,a[][];
int num_edge,head[N];
int dis[N],INF,pre[N];
int dx[]= {,-,,,},dy[]= {,,,-,};
char st[];
queue<int>q;
struct node
{
int to,next,Flow,Cost;
} edge[M*]; void add(int u,int v,int l,int c)
{
edge[++num_edge].to=v;
edge[num_edge].next=head[u];
edge[num_edge].Flow=l;
edge[num_edge].Cost=c;
head[u]=num_edge;
} bool Spfa(int s,int e)
{
memset(dis,0x7f,sizeof(dis));
memset(pre,-,sizeof(pre));
dis[s]=;
used[s]=true;
q.push(s);
while (!q.empty())
{
int x=q.front();
q.pop();
for (int i=head[x]; i!=; i=edge[i].next)
if (dis[x]+edge[i].Cost<dis[edge[i].to] && edge[i].Flow>)
{
dis[edge[i].to]=dis[x]+edge[i].Cost;
pre[edge[i].to]=i;
if (!used[edge[i].to])
{
used[edge[i].to]=true;
q.push(edge[i].to);
}
}
used[x]=false;
}
return dis[e]!=INF;
} int MCMF(int s,int e)
{
int Fee=;
while (Spfa(s,e))
{
int d=INF;
for (int i=e; i!=s; i=edge[((pre[i]-)^)+].to)
d=min(d,edge[pre[i]].Flow);
for (int i=e; i!=s; i=edge[((pre[i]-)^)+].to)
{
edge[pre[i]].Flow-=d;
edge[((pre[i]-)^)+].Flow+=d;
}
Fee+=d*dis[e];
}
return Fee;
} int main()
{
memset(&INF,0x7f,sizeof(INF));
s=,e=;
scanf("%d%d",&n,&m);
for (int i=; i<=n; ++i)
{
scanf("%s",st);
for (int j=; j<=m; ++j)
{
if (st[j-]=='U') a[i][j]=;
if (st[j-]=='D') a[i][j]=;
if (st[j-]=='L') a[i][j]=;
if (st[j-]=='R') a[i][j]=;
add(s,id(i,j),,);
add(id(i,j),s,,);
add(id(i,j)+m*n,e,,);
add(e,id(i,j)+m*n,,);
}
}
for (int i=; i<=n; ++i)
for (int j=; j<=m; ++j)
for (int k=; k<=; ++k)
{
int x=i+dx[k],y=j+dy[k];
if (x<) x=n;
if (x>n) x=;
if (y<) y=m;
if (y>m) y=;
add(id(i,j),id(x,y)+m*n,,(k!=a[i][j]));
add(id(x,y)+m*n,id(i,j),,-(k!=a[i][j]));
}
printf("%d",MCMF(s,e));
}