首页 > 代码库 > bzoj3171: [Tjoi2013]循环格
bzoj3171: [Tjoi2013]循环格
3171: [Tjoi2013]循环格
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 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
RRRD
URLL
LRRR
Sample Output
2
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\n",ans);63 }
bzoj3171: [Tjoi2013]循环格
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。