【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3171
【题目大意】
一个循环格就是一个矩阵，其中所有元素为箭头，指向相邻四个格子。
每个元素有一个坐标（行，列），其中左上角元素坐标为（0,0）。给定一个起始位置（r，c）
你可以沿着箭头防线在格子间行走。即如果（r,c）是一个左箭头，那么走到（r，c-1）;
如果是右箭头那么走到（r，c+1）；如果是上箭头那么走到（r-1，c）；
如果是下箭头那么走到（r+1，c）；每一行和每一列都是循环的，
即如果走出边界，你会出现在另一侧。一个完美的循环格是这样定义的：
对于任意一个起始位置，你都可以i沿着箭头最终回到起始位置。
如果一个循环格不满足完美，你可以随意修改任意一个元素的箭头直到完美。
给定一个循环格，你需要计算最少需要修改多少个元素使其完美。
【题解】
我们发现一个完美的循环格每个元素都只有一个入度和一个出度，
因此我们将其拆分为入点和出现，入点连汇点，出点连源点，流量为1，费用为0，
对于每个箭头指向的反向，连相应的出点到入点，流量为1，费用为0，
对于相邻但是箭头不指向的地方，我们将其相互连接，流量为1，费用为1，
求最小费用最大流即答案。
【代码】
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x7fffffff,N=1010;
int S,T,cnt,ans,d[N],q[N],from[N],g[N],flow,tot;
bool in[1010];
struct edge{int from,to,nxt,c,v;}e[100010];
void add(int u,int v,int w,int c){
e[++cnt].from=u;e[cnt].to=v;
e[cnt].nxt=g[u];g[u]=cnt;
e[cnt].c=c;e[cnt].v=w;
}void add_edge(int u,int v,int w,int c){add(u,v,w,c);add(v,u,0,-c);}
bool spfa(){
for(int i=S;i<=T;i++)d[i]=INF;
int t=0,w=1;d[S]=0;in[S]=1;q[0]=S;
while(t!=w){
int now=q[t];t++;if(t==T)t=0;
for(int i=g[now];i;i=e[i].nxt)
if(e[i].v&&d[e[i].to]>d[now]+e[i].c){
d[e[i].to]=d[now]+e[i].c;from[e[i].to]=i;
if(!in[e[i].to]){in[e[i].to]=1;q[w++]=e[i].to;if(w==T)w=0;}
}in[now]=0;
}return(d[T]!=INF);
}
void mcf(){
int x=INF;
for(int i=from[T];i;i=from[e[i].from])x=min(x,e[i].v);flow+=x;
for(int i=from[T];i;i=from[e[i].from]){e[i].v-=x;e[i^1].v+=x;ans+=e[i].c*x;}
}
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int R,C,mp[20][20];
char str[20][20];
int main(){
while(~scanf("%d%d",&R,&C)){
memset(g,0,sizeof(g));
cnt=1; ans=flow=0;
S=0,T=C*R*2+1;
for(int i=1;i<=R;i++)scanf("%s",str[i]+1);
for(int i=1;i<=R;i++)for(int j=1;j<=C;j++){
if(str[i][j]=='U')mp[i][j]=1;
if(str[i][j]=='D')mp[i][j]=0;
if(str[i][j]=='L')mp[i][j]=3;
if(str[i][j]=='R')mp[i][j]=2;
for(int k=0;k<4;k++){
int x=i+dx[k],y=j+dy[k];
if(x>R)x=1;if(x<1)x=R;
if(y>C)y=1;if(y<1)y=C;
if(k==mp[i][j])add_edge((i-1)*C+j,(x-1)*C+y+C*R,1,0);
else add_edge((i-1)*C+j,(x-1)*C+y+C*R,1,1);
}add_edge(S,(i-1)*C+j,1,0);
add_edge((i-1)*C+j+C*R,T,1,0);
}while(spfa())mcf();
printf("%d\n",ans);
}return 0;
}