BZOJ 3171 Tjoi 2013ループグリッド

トランスファゲート
Description
1つのループ・グリッドは、すべての要素が矢印であり、隣接する4つのグリッドを指します.各要素には、左上隅の要素座標が(0,0)の座標(行、列)があります.開始位置(r,c)を指定すると、矢印の線に沿って格子間を歩くことができます.すなわち、(r,c)が左矢印の場合は(r,c-1)、右矢印の場合は(r,c+1)、上矢印の場合は(c+1)、(r-1,c);下矢印であれば(r+1,c);各行と各列は循環している.すなわち、境界を出ると反対側に現れる.完璧な循環格子は、任意の開始位置について、iは矢印に沿って最終的に開始位置に戻ることができる.もし1つの循環格子が完璧でない場合、任意の要素の矢印を完璧に変更することができる.このループ・グリッドでは、少なくともどれだけの要素を完璧に修正する必要があるかを計算する必要があります.
Input
1行目の2つの整数R,C.行と列を表し、次にR行、各行C文字LRUD、左右上下を表す.
Output
与えられたループ・グリッドが完璧になるように、最小でどれだけの要素を変更する必要があるかを示す整数
Sample Input
3 4
RRRD
URLL
LRRR
Sample Output
2
HINT
1<=R,C<=15
この問題はどうしますか.私たちはどのようにして最も優れた意思決定の方法を考え出すのが難しいので、いっそ彼を放っておきます!この問題は私たちに1つの経典の問題を思い出させました:“1つの図を与えて、判断はすべて少なくとも1つの環の中に少なくあります”.1つの方法は、ネットワークストリームを走り、各ポイントを2つに分解し、1つを進み、ソースポイントをそれに接続し、1つを出し、それを送金ポイントに接続し、最大ストリームを走ると、答えが得られます.この問題はあまり悪くないのではないでしょうか.道を変えることができて、それでは私达は1枚の“四通八达”の図につながって、もとの方向の费用は0で、残りの费用は1です.費用の流れを走ると、答えは費用です.

/************************************************************** Problem: 3171 User: geng4512 Language: C++ Result: Accepted Time:4 ms Memory:1236 kb ****************************************************************/

#include<algorithm>
#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
#define MAXN 10005
using namespace std;
int n, m, S, T, dd[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
char mp[30][30];
int hsh[200];
struct Node { int v, w, f, nxt; } e[MAXN<<1];
int Adj[MAXN], ecnt = 1, cost, dis[MAXN];
int vis[MAXN];
inline void Add(int u, int v, int w, int f) {
    ++ ecnt; e[ecnt].v = v; e[ecnt].w = w; e[ecnt].f = f; e[ecnt].nxt = Adj[u]; Adj[u] = ecnt;
    ++ ecnt; e[ecnt].v = u; e[ecnt].w = -w; e[ecnt].f = 0; e[ecnt].nxt = Adj[v]; Adj[v] = ecnt;
}
bool Upd() {
    int tmp = INF;
    for(int u = 0; u <= T; ++ u) if(vis[u])
        for(int i = Adj[u]; i; i = e[i].nxt)
                if(!vis[e[i].v] && e[i].f)
                    tmp = min(tmp, dis[e[i].v] + e[i].w - dis[u]);
    if(tmp == INF) return 0;
    for(int u = 0; u <= T; ++ u) if(vis[u]) dis[u] += tmp;
    return 1;
}
int Aug(int u, int augco) {
    if(u == T) {
        cost += dis[S] * augco;
        return augco;
    }
    int augc = augco, delta, v;
    vis[u] = 1;
    for(int i = Adj[u]; i; i = e[i].nxt) {
        v = e[i].v;
        if(e[i].f && !vis[v] && dis[u] - e[i].w == dis[v]) {
            delta = Aug(v, min(e[i].f, augc));
            augc -= delta; e[i].f -= delta; e[i^1].f += delta;
            if(!augc) return augco;
        }
    }
    return augco - augc;
}
int ZKW() {
    do {
        do memset(vis, 0, sizeof vis); while(Aug(S, INF));
    } while(Upd());
    return cost;
}
int main() {
    scanf("%d%d", &n, &m);
    S = 2*n*m; T = S + 1;
    hsh['L'] = 3; hsh['R'] = 1; hsh['U'] = 2; hsh['D'] = 0;
    for(int i = 0; i < n; ++ i) {
        scanf("%s", mp[i]);
        for(int j = 0; j < m; ++ j) {
            Add(i*m+j, T, 0, 1);
            Add(S, i*m+j+n*m, 0, 1);
            for(int k = 0; k < 4; ++ k) {
                int x = i + dd[k][0], y = j + dd[k][1];
                if(x < 0) x = n-1;
                if(x == n) x = 0;
                if(y < 0) y = m-1;
                if(y == m) y = 0;
                Add(i*m+j+n*m, x*m+y, hsh[mp[i][j]] != k, 1);
            }
        }
    }
    printf("%d
", ZKW());
}