bzoj3171: [Tjoi2013]循环格

3171: [Tjoi2013]循环格

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 871 Solved: 551
[Submit][Status][Discuss]

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

HINT

首先有一个结论每个点只存在于一个环中所以入度和出度都为1..（没想到结论退役系列）

所以考虑用流

拆一波点

S向入点连边容量为1 出点向T连边容量为1

向四联通的点连边容量为1费用为1...（如果是原来就有的箭头则费用为0）

 1 #include<bits/stdc++.h>
 2 #define rep(i,l,r) for(int i=l;i<=r;++i)
 3 using namespace std;
 4 const int N=102333,inf=2147483647;
 5 struct Edge{
 6     int to,next,from,c,w;
 7 }e[1000000];
 8 const int xx[4]={0,0,-1,1};
 9 const int yy[4]={-1,1,0,0};
10 int head[N],tot=1,ans,dis[N],from[N],T,mp[100][100],nx,ny,cnt,n,m,num[100][100][2];
11 bool used[N];
12 char s[100][100];
13 inline void ins(int u,int v,int w,int cost) {
14      e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; e[tot].c=cost; e[tot].from=u;
15 }
16 
17 inline bool spfa() {
18      queue<int> q; for(int i=0;i<=T;i++) dis[i]=inf; dis[0]=0; q.push(0); used[0]=1;  
19      while(!q.empty()) {
20           int x=q.front(); q.pop();
21           for(int k=head[x];k;k=e[k].next) 
22            if(e[k].w>0&&dis[x]+e[k].c<dis[e[k].to]){
23                   dis[e[k].to]=dis[x]+e[k].c; from[e[k].to]=k;
24                   if(!used[e[k].to]) {
25                         used[e[k].to]=1; q.push(e[k].to);
26                   }
27             }
28            used[x]=0;
29      }
30      if(dis[T]==inf) return 0;else return 1;
31 }
32 
33 inline void run() {
34      int x=inf;
35      for(int k=from[T];k;k=from[e[k].from]) x=min(x,e[k].w);
36      for(int k=from[T];k;k=from[e[k].from]) {
37           e[k].w-=x; e[k^1].w+=x; ans+=e[k].c*x;
38      }
39 }
40 inline void insert(int u,int v,int w,int c){
41     ins(u,v,w,c); ins(v,u,0,-c);
42 }
43 int main(){
44     scanf("%d%d",&n,&m);
45     rep(i,1,n) scanf("%s",s[i]+1);
46     rep(i,1,n) rep(j,1,m) if(s[i][j]=='L') mp[i][j]=0;else if(s[i][j]=='R') mp[i][j]=1;
47                           else if(s[i][j]=='U') mp[i][j]=2;else mp[i][j]=3;
48     rep(i,1,n) rep(j,1,m) num[i][j][0]=++cnt,num[i][j][1]=++cnt;
49     T=cnt+1;
50     rep(i,1,n) rep(j,1,m) insert(0,num[i][j][0],1,0),insert(num[i][j][1],T,1,0);
51     rep(i,1,n) rep(j,1,m) {
52         rep(l,0,3) {
53             nx=i+xx[l]; ny=j+yy[l];
54 //            if(nx<1||nx>n||ny<1||ny>m) continue;
55             if(nx<1) nx=n; if(nx>n) nx=1;
56             if(ny<1) ny=m; if(ny>m) ny=1;
57             if(mp[i][j]==l) insert(num[i][j][0],num[nx][ny][1],1,0);
58             else insert(num[i][j][0],num[nx][ny][1],1,1);
59         }
60     }
61     while(spfa()) run();
62     printf("%d
",ans);
63 }

View Code