P3965 [TJOI2013] 循环格

· · 题解

思路：

首先显然每个点出度为 1，那么可以推出所有循环间两两没有交集，不然交集那里会出现出度为 2 的矛盾。

所以图由若干个互不相交的环构成，那么所有点入度也为 1，且这也是充要条件。

为了确保出入度平衡，将每个点拆为左右两个点：

显然此时最大流为 n，一定能跑满（因为一定存在解），那么跑最小费用最大流就行了。

时间复杂度为 O((rc)^3)。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 505, M = 1e5 + 10;
const int INF = 1e9;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
namespace MCMF {
    struct edge {
        int v, c, w, nxt;
    } e[M];
    int s, t, node, idx = 1;
    int head[N], now[N];
    ll dis[N];
    bool vis[N];

    inline void add(int u, int v, int c, int w){
        e[++idx] = {v, c, w, head[u]};
        head[u] = idx;
    }
    inline void Add(int u, int v, int c, int w){
        // cerr << "edge: " << u << ' ' << v << ' ' << c << ' ' << w << '\n';
        add(u, v, c, w);
        add(v, u, 0, -w);
    }

    inline bool spfa(){
        for(int i = 0; i <= node; ++i)
          dis[i] = INF;
        deque<int> q;
        q.push_front(s);
        dis[s] = 0, vis[s] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop_front();
            vis[u] = 0;
            for(int i = head[u]; i; i = e[i].nxt){
                int v = e[i].v, c = e[i].c, w = e[i].w;
                if(dis[v] > dis[u] + w && c){
                    dis[v] = dis[u] + w;
                    if(!vis[v]){
                        if(!q.empty() && dis[v] > dis[q.front()])
                          q.push_back(v);
                        else
                          q.push_front(v); 
                        vis[v] = 1;
                    }
                }
            }
        }
        return dis[t] != INF;
    }

    inline ll dfs(int u, ll mf, ll &ans){
        if(u == t)
          return mf;
        vis[u] = 1;
        ll sum = 0;
        for(int i = now[u]; i && mf; i = e[i].nxt){
            now[u] = i;
            int v = e[i].v, c = e[i].c, w = e[i].w;
            if(!vis[v] && dis[v] == dis[u] + w && c){
                ll flow = dfs(v, min((ll)c, mf), ans);
                if(!flow)
                  dis[v] = INF;
                ans += flow * w;
                e[i].c -= flow;
                e[i ^ 1].c += flow;
                sum += flow;
                mf -= flow;
            }
        }
        vis[u] = 0;
        return sum;
    }

    inline pair<ll, ll> dinic(){
        ll sum = 0, ans = 0;
        while(spfa()){
            memcpy(now, head, sizeof(int) * (node + 1));
            sum += dfs(s, INF, ans);
        }
        return {sum, ans};
    }
}
char c;
int n, m, s, t;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline char get(){
    char c = getchar();
    while(c != 'L' && c != 'R' && c != 'U' && c != 'D')
      c = getchar();
    return c;
}
inline int id(int i, int j, int k){
    return (i - 1) * m + j + k * n * m;
}
int main(){
    n = read(), m = read();
    MCMF::s = s = 0, MCMF::t = MCMF::node = t = 2 * n * m + 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            c = get();
            int op = (c == 'L' || c == 'R') ? (c == 'L' ? 1 : 0) : (c == 'U' ? 3 : 2);
            for(int k = 0; k < 4; ++k){
                int di = i + dx[k], dj = j + dy[k];
                if(di > n) di = 1;
                if(!di) di = n;
                if(dj > m) dj = 1;
                if(!dj) dj = m;
                MCMF::Add(id(i, j, 0), id(di, dj, 1), 1, k != op);
            }
            MCMF::Add(s, id(i, j, 0), 1, 0);
            MCMF::Add(id(i, j, 1), t, 1, 0);
        }
    }
    write(MCMF::dinic().se);
    return 0;
}