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
RRRD
URLL
LRRR
Sample Output
2
HINT
1<=R,L<=15
一开始看错题了，以为是每个格子都要回到(0,0)。
原来是每个格子回到原来的位置。
这样可以说明每个点入度和出度都为1。
于是拆点建立二分图，相邻的连上边，流量为1费用为是否不能到达。
然后跑最小费用最大流即可。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10050
#define M 400050
#define S (2*n*m+1)
#define T (2*n*m+2)
#define inf 1<<30
#define p(i,j) ((i-1)*m+j)
int n,m,head[N],to[M],nxt[M],val[M],flow[M],cnt=1,path[N];
int Q[N],l,r,dis[N],inq[N];
char s[18][18];
int tx[]={0,1,0,-1};
int ty[]={1,0,-1,0};
inline void add(int u,int v,int f,int c) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f; val[cnt]=c;
to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0; val[cnt]=-c;
}
bool spfa() {
memset(dis,0x3f,sizeof(dis));
memset(path,0,sizeof(path));
dis[S]=0; l=r=0; Q[r++]=S;
int i;
while(l!=r) {
int x=Q[l++]; inq[x]=0; if(l==T) l=0;
for(i=head[x];i;i=nxt[i]) {
if(dis[to[i]]>dis[x]+val[i]&&flow[i]) {
dis[to[i]]=dis[x]+val[i];
path[to[i]]=i^1;
if(!inq[to[i]]) {
Q[r++]=to[i]; if(r==T) r=0;
}
}
}
}
return path[T];
}
void mcmf() {
int ans=0;
while(spfa()) {
// puts("FUCK");
int nf=1<<30;
int i;
for(i=T;i!=S;i=to[path[i]]) {
nf=min(nf,flow[path[i]^1]);
}
for(i=T;i!=S;i=to[path[i]]) {
ans+=nf*val[path[i]^1];
flow[path[i]^1]-=nf;
flow[path[i]]+=nf;
}
}
printf("%d\n",ans);
}
int main() {
scanf("%d%d",&n,&m);
int i,j,k;
for(i=1;i<=n;i++) scanf("%s",s[i]+1);
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
add(S,p(i,j),1,0);
add(p(i,j)+n*m,T,1,0);
int p=0;
if(s[i][j]=='R') p=0;
else if(s[i][j]=='D') p=1;
else if(s[i][j]=='L') p=2;
else p=3;
for(k=0;k<4;k++) {
int di=i+tx[k],dj=j+ty[k];
if(di==0) di=n; if(di==n+1) di=1;
if(dj==0) dj=m; if(dj==m+1) dj=1;
add(p(i,j),p(di,dj)+n*m,1,p!=k);
}
}
}
mcmf();
}