重点：如果满流一定存在许多个欧拉回路。于是费用流。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define maxv 500 #define maxe 1000050 #define maxn 20 #define inf 2000000000 using namespace std; int n,m,map[maxn][maxn],dis[maxv],nume=1,g[maxv],s,t,pree[maxv],prev[maxv]; int dx[]={0,0,0,-1,1},dy[]={0,-1,1,0,0}; char pp[maxn]; bool vis[maxv]; queue <int> q; struct edge { int v,f,c,nxt; }e[maxe]; void get(int x,int y) { if (pp[y-1]=='L') map[x][y]=1; else if (pp[y-1]=='R') map[x][y]=2; else if (pp[y-1]=='U') map[x][y]=3; else map[x][y]=4; } void addedge(int u,int v,int f,int c) { e[++nume].v=v;e[nume].f=f;e[nume].c=c;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0;e[nume].c=-c;e[nume].nxt=g[v];g[v]=nume; } int p(int x,int y) { return (x-1)*m+y; } void build() { s=0;t=2*n*m+1; for (int i=1;i<=n*m;i++) { addedge(s,i,1,0); addedge(i+n*m,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 tx=(i+dx[k]+n)%n,ty=(j+dy[k]+m)%m; if (!tx) tx=n;if (!ty) ty=m; if ((tx==i) && (ty==j)) continue; if (map[i][j]==k) addedge(p(i,j),n*m+p(tx,ty),1,0); else addedge(p(i,j),n*m+p(tx,ty),1,1); } } bool spfa() { for (int i=s;i<=t;i++) {pree[i]=prev[i]=-1;dis[i]=inf;vis[i]=false;} q.push(s);vis[s]=true;dis[s]=0; while (!q.empty()) { int head=q.front();q.pop(); for (int i=g[head];i;i=e[i].nxt) { int v=e[i].v; if ((e[i].f) && (dis[v]>dis[head]+e[i].c)) { dis[v]=dis[head]+e[i].c; pree[v]=i;prev[v]=head; if (!vis[v]) {q.push(v);vis[v]=true;} } } vis[head]=false; } if (dis[t]==inf) return false; return true; } int dinic() { int u=t,low=inf; while (u!=s) { low=min(low,e[pree[u]].f); u=prev[u]; } u=t; while (u!=s) { e[pree[u]].f-=low;e[pree[u]^1].f+=low; u=prev[u]; } return dis[t]*low; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",pp); for (int j=0;j<m;j++) get(i,j+1); } build(); int min_cost=0; while (spfa()) min_cost+=dinic(); printf("%d ",min_cost); return 0; }