【BZOJ 3171】 [Tjoi2013]循环格

Description

一个循环格就是一个矩阵,其中所有元素为箭头,指向相邻四个格子。每个元素有一个坐标(行,列),其中左上角元素坐标为(0,0)。给定一个起始位置(r,c)

,你可以沿着箭头防线在格子间行走。即如果(r,c)是一个左箭头,那么走到(r,c-1);如果是右箭头那么走到(r,c+1);如果是上箭头那么走到(r-1,c);如果是下箭头那么走到(r+1,c);每一行和每一列都是循环的,即如果走出边界,你会出现在另一侧。
一个完美的循环格是这样定义的:对于任意一个起始位置,你都可以i沿着箭头最终回到起始位置。如果一个循环格不满足完美,你可以随意修改任意一个元素的箭头直到完美。给定一个循环格,你需要计算最少需要修改多少个元素使其完美。

Input

第一行两个整数R,C。表示行和列,接下来R行,每行C个字符LRUD,表示左右上下。

Output

一个整数,表示最少需要修改多少个元素使得给定的循环格完美

Sample Input

3 4
RRRD
URLL
LRRR

Sample Output

2

HINT

1<=R,L<=15

 
或许很明显,但我真真没看出这是一个网络流
hzwer题解
每个格子入度为一,出度为一
拆点,每个格子向它周围格子的右部点连边,费用为0或1,跑最小费用流
 #include<cstdio>
#include<cstring>
using namespace std;
const int N=,inf=;
struct ee{int to,next,f,w;}e[N*N*];
int S,T,cnt=,n,k,ans,timer,m,u,v,w;
int head[N*N],dis[N*N],pre[N*N],q[N*N],map[N][N];
bool inq[N];
int fx[]={-,,,},fy[]={,,-,};
void ins(int u,int v,int f,int w){
e[++cnt].to=v,e[cnt].next=head[u],e[cnt].f=f,e[cnt].w=w,head[u]=cnt;
e[++cnt].to=u,e[cnt].next=head[v],e[cnt].f=,e[cnt].w=-w,head[v]=cnt;
} bool spfa(){
for (int i=;i<=T;i++) dis[i]=inf;
int h=,t=;
q[t]=S;dis[S]=;inq[S]=;
while (h!=t){
int now=q[++h];if(h==T) h=;
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (dis[v]>dis[now]+e[i].w&&e[i].f){
dis[v]=dis[now]+e[i].w;
pre[v]=i;
if (!inq[v]){
q[++t]=v;if (t==T) t=;
inq[v]=;
}
}
}
inq[now]=;
}
if (dis[T]==inf) return ;
return ;
} void updata(){
int tmp=T;
while (tmp!=S){
int l=pre[tmp],v=e[l].to;
e[l].f-=;e[l^].f+=;
tmp=e[l^].to;
}
ans+=dis[T];
}
int main(){
scanf("%d%d",&n,&m);
T=n*m*+;
char s[];
for(int i=;i<=n;i++){
scanf("%s",s+);
for (int j=;j<=m;j++){
if(s[j]=='U')map[i][j]=;
if(s[j]=='D')map[i][j]=;
if(s[j]=='L')map[i][j]=;
if(s[j]=='R')map[i][j]=;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
int u=(i-)*m+j;
ins(S,u,,);ins(u+n*m,T,,);
for(int k=;k<;k++){
int nx=i+fx[k],ny=j+fy[k];
if(nx>n)nx=;if(nx<)nx=n;
if(ny>m)ny=;if(ny<)ny=m;
if(k==map[i][j]) ins(u,(nx-)*m+ny+m*n,,);
else ins(u,(nx-)*m+ny+m*n,,);
}
}
while (spfa())
updata();
printf("%d",ans);
}
上一篇:Selenium clear()方法无法清掉数据


下一篇:ServiceDesk Plus 服务管理自动指派工单功能