bzoj 3171: [Tjoi2013]循环格 最小费用最大流

题目大意:

题解:

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

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

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

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

跑最小费用最大流即可.

#include <cstdio>

#include <cstring>

#include <cassert>

#include <algorithm>

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<b ? a:b;}

const int maxnode = 512;

const int maxedge = 4096;

struct Edge{

    int to,next,cap,cost;

}G[maxedge<<1];

int head[maxnode],cnt=1;

void add(int u,int v,int c,int d){

    G[++cnt].to = v;

    G[cnt].next = head[u];

    head[u] = cnt;

    G[cnt].cap = c;

    G[cnt].cost = d;

}

inline void insert(int u,int v,int c,int d){

    add(u,v,c,d);add(v,u,0,-d);

}

#define v G[i].to

const int lim = maxnode<<1;

int dis[maxnode],p[maxnode],q[lim + 10],flow[maxnode];

int l,r,S,T,ans;bool inq[maxnode];

const int inf = 0x3f3f3f3f;

bool spfa(){

    memset(dis,0x3f,sizeof dis);

    dis[S] = 0;flow[S] = inf;

    inq[S] = true;l = 0;r = -1;

    q[++r] = S;

    while(l <= r){

        int u = q[l % lim];++l;

        for(int i = head[u];i;i=G[i].next){

            if(dis[v] > 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;

}