[TJOI2013]循环格

题目

我也不知道我建了个什么图，之后随便跑了跑就过了

发现要求形成一个环，改边的方向需要\(1\)的代价

根据网络流的套路开始拆点

1. 每个点拆成两个点，\(S\)向入点连流量为\(1\)的边，出点向\(T\)连流量为\(1\)的边

2. 对于那些方向改变的边，费用都是\(1\)，否则是\(0\)

这样为什么是对的呢，考虑一下如果形成了一个环，那么每一点的流量都会在下一个点被排掉，显然之后环才能保证所有的点的流量都被排掉

当然这道题的主流做法是利用每一个点的入度出度仅为\(1\)的性质，发挥网络流调整的特性来做的

其实本质是一样的因为图建出来是一样的

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=505;
const int inf=999999999;
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int n,m,S,T,num=1;
std::queue<int> q;
struct E{int v,nxt,w,f;}e[maxn*maxn];
int head[maxn],vis[maxn],d[maxn];
inline void C(int x,int y,int w,int f) {
    e[++num].v=y;e[num].nxt=head[x];
    head[x]=num;e[num].f=f;e[num].w=w;
}
inline void add(int x,int y,int w,int f) {C(x,y,w,f),C(y,x,-1*w,0);}
char map[20][20];
int in[20][20],out[20][20];
const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
inline int SPFA() {
    for(re int i=S;i<=T;i++) d[i]=inf,vis[i]=0;
    d[T]=0,q.push(T);
    while(!q.empty()) {
        int k=q.front();q.pop();vis[k]=0;
        for(re int i=head[k];i;i=e[i].nxt)
        if(e[i^1].f&&d[e[i].v]>d[k]+e[i^1].w) {
            d[e[i].v]=d[k]+e[i^1].w;
            if(!vis[e[i].v]) q.push(e[i].v),vis[e[i].v]=0;
        }
    }
    return d[S]<inf;
}
int dfs(int x,int now) {
    if(x==T||!now) return now;
    vis[x]=1;int flow=0,ff;
    for(re int i=head[x];i;i=e[i].nxt)
    if(!vis[e[i].v]&&e[i].f&&d[e[i].v]==d[x]+e[i^1].w){
        ff=dfs(e[i].v,min(e[i].f,now));
        if(ff<=0) continue;
        now-=ff,flow+=ff,e[i].f-=ff,e[i^1].f+=ff;
        if(!now) break;
    }
    return flow;
}
inline int check(char A) {
    if(A=='L') return 0;if(A=='R') return 1;
    if(A=='U') return 2;return 3;
}
int main() {
    n=read(),m=read();
    for(re int i=1;i<=n;i++) scanf("%s",map[i]+1);
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) in[i][j]=++T;
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) out[i][j]=++T;
    ++T;
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) add(S,in[i][j],0,1),add(out[i][j],T,0,1);
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) 
            map[i][j]=check(map[i][j]);
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) 
            for(re int k=0;k<4;k++) {
                int x=i+dx[k],y=j+dy[k];
                if(x<1) x=n;if(y<1) y=m;
                if(x>n) x=1;if(y>m) y=1;
                add(in[i][j],out[x][y],k!=map[i][j],1);
            }
    int ans=0;
    while(SPFA()) {
        vis[T]=1;
        while(vis[T]) {
            for(re int i=S;i<=T;i++) vis[i]=0;
            ans+=dfs(S,inf)*d[S];
        }
    }
    printf("%d",ans);
    return 0;
}

[TJOI2013]循环格

原文：https://www.cnblogs.com/asuldb/p/10554818.html