题解 P3965 【[TJOI2013]循环格】

· · 题解

题目大意

在网格图中，每个点有一个方向，经过这个点之后要往这个方向走一格走到下一个点，如果走出网格图就从另一边进去，这些方向可以更改，要求从任意一点出发，经过若干步之后能重新回到此点

分析

每个点都有指向，那么边数就与点数相同，每个点的出度就是1

要求能重新回到这个点，这个点的入度也至少是1，显然，每个点的入度都是1

既然每个点的出、入度都是1，那么就会形成若干个环，每个点的出边连向另一个点，某个点的出边连向这个点

把一个点拆成2个点，整张图上每个出点与入点一一匹配

既然这些点都一一对应，那就可以跑带权二分图匹配了

做法

让每个点往4个方向连边，容量为1，费用为是否需要改变方向

建立超级源点与超级汇点，连上每个点，显然容量为1，费用为0

int now=get(i,j);
ADD(S,now,1,0),ADD(now+k,T,1,0);
ADD(now,get(i-1,j)+k,1,c[j]!='U');
ADD(now,get(i+1,j)+k,1,c[j]!='D');
ADD(now,get(i,j-1)+k,1,c[j]!='L');
ADD(now,get(i,j+1)+k,1,c[j]!='R');

此处get(i,j)是把二维的矩阵转化为一维，在跑费用流的时候较方便

int get(int x,int y){
    x=x<1?x+n:(x>n?x-n:x);
    y=y<1?y+m:(y>m?y-m:y);
    return (x-1)*m+y;
}

费用流打版子即可

具体细节请看代码

解法

带权二分图匹配，费用流

代码

#include<bits/stdc++.h>
#define IN inline
using namespace std;
const int maxn=10005,maxe=maxn<<3,INF=1<<30;
int n,m,S,T,k,ans;
int tot=1,lnk[maxn];
int que[maxn],flow[maxn],dis[maxn],pre[maxn],lst[maxn];
bool vis[maxn];
char c[20];

struct edge{
    int to,nxt,flow,dis;
}e[maxe];

IN int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

IN int get(int x,int y){
    x=x<1?x+n:(x>n?x-n:x);
    y=y<1?y+m:(y>m?y-m:y);
    return (x-1)*m+y;
}
/*以下是费用流板子*/
IN void add_e(int x,int y,int f,int d){
    e[++tot]=(edge){y,lnk[x],f,d};
    lnk[x]=tot;
}
void ADD(int x,int y,int f,int d){
    add_e(x,y,f,d),add_e(y,x,0,-d);
}

bool SPFA(int s,int t){
    for(int i=1;i<=T;i++) flow[i]=dis[i]=INF,pre[i]=-1;
    int hed=0,til=1;
    que[1]=s,vis[s]=1,dis[s]=0,pre[t]=-1;
    while(hed!=til){
        int x=que[hed=(++hed)%maxn];
        vis[x]=0;
        for(int j=lnk[x];j;j=e[j].nxt){
            int y=e[j].to;
            if(e[j].flow&&dis[y]>dis[x]+e[j].dis){
                dis[y]=dis[x]+e[j].dis;
                flow[y]=min(flow[x],e[j].flow);
                pre[y]=x;
                lst[y]=j;
                if(!vis[y]){
                    vis[y]=1;
                    que[til=(++til)%maxn]=y;
                }
            }
        }
    }
    return pre[t]!=-1;
}

void MCMF(int s,int t){
    while(SPFA(s,t)){
        ans+=(LL)flow[t]*dis[t];
        int now=t;
        while(now!=s){
            e[lst[now]].flow-=flow[t];
            e[lst[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
    return;
}
/*以上是费用流板子*/
int main(){
    freopen("P3965.in","r",stdin);
    freopen("P3965.out","w",stdout);
    n=read(),m=read(),k=n*m;//k是矩阵大小，把每个点拆成x（出点）与x+k（入点）
    S=2*n*m+1,T=2*n*m+2;
    for(int i=1;i<=n;i++){
        scanf("%s",c+1);
        for(int j=1;j<=m;j++){
            int now=get(i,j);
            ADD(S,now,1,0),ADD(now+k,T,1,0);
            ADD(now,get(i-1,j)+k,1,c[j]!='U');
            ADD(now,get(i+1,j)+k,1,c[j]!='D');
            ADD(now,get(i,j-1)+k,1,c[j]!='L');
            ADD(now,get(i,j+1)+k,1,c[j]!='R');
        }
    }
    MCMF(S,T);
    printf("%d\n",ans);
    return 0;
}