题目大意:

题解:

首先我们很容易发现一个结论:

出现完美循环当且仅当所有点的出入度均为1

所以利用这个性质,我们将每个点拆成两个点

S连向出点,入点连向T,然后出点向上下左右的入点连边

跑最小费用最大流即可.

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;inline void read(int &x){    x=0;char ch;bool flag = false;    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a
         dis[u] + G[i].cost && G[i].cap){                dis[v] = dis[u] + G[i].cost;                flow[v] = min(flow[u],G[i].cap);                p[v] = i;                if(!inq[v]){                    q[++r % lim] = v;                    inq[v] = true;                }            }        }inq[u] = false;    }if(dis[T] == dis[0]) return false;    ans += dis[T]*flow[T];    for(int u = T;u != S;u = G[p[u]^1].to){        G[p[u]].cap -= flow[T],G[p[u]^1].cap += flow[T];    }    return true;}#undef v#define f(x,y) ((x-1)*m + y)int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};inline int id(const char &ch){    if(ch == 'U') return 3;    if(ch == 'D') return 2;    if(ch == 'L') return 1;    if(ch == 'R') return 0;    return -1;}int main(){    int n,m;read(n);read(m);    S = maxnode - 5;T = S+1;    char ch;    for(int i=1,x;i<=n;++i){        for(int j=1;j<=m;++j){            insert(f(i,j)<<1,T,1,0);            insert(S,f(i,j)<<1|1,1,0);            while(ch=getchar(),ch<'!');            x = id(ch);if(x == -1) assert(0);            for(int k=0;k<4;++k){                int nx = i + dx[k];if(nx == n+1) nx = 1;if(nx == 0) nx = n;                int ny = j + dy[k];if(ny == m+1) ny = 1;if(ny == 0) ny = m;                insert(f(i,j)<<1|1,f(nx,ny)<<1,1,x != k);            }        }    }    while(spfa());    printf("%d\n",ans);    getchar();getchar();    return 0;}