Bzoj 3171: [Tjoi2013]循环格费用流

3171: [Tjoi2013]循环格

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 741 Solved: 463
[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<=R,L<=15

Source

题解：

这道题就是让每个点都在至少一个环里。

于是就可以用费用流。

一个格子只能选一次，所以入度出度都为1。

然后拆点。

左边为出点，右边为入点。

从S向所有Xi连费用为0，容量为1的边。(从X出发)

Yi向T连费用为0，容量为1的边。(到达Y)

从X的Xi向Y的Yj连容量为1，费用为0。(原图中有的边)

原图中没有的剩下三个方向连容量为1，费用为1。

跑最小费用最大流即可。。。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define INF 1e9
  4 struct node
  5 {
  6     int begin,end,cap,value,next;
  7 }edge[2710];
  8 int cnt,Head[620],c,S,T,ans,q[620],dis[620],from[620];
  9 bool vis[620];
 10 char a[20][20];
 11 int fx[5]={0,0,1,-1};
 12 int fy[5]={1,-1,0,0};
 13 void addedge(int bb,int ee,int cc,int vv)
 14 {
 15     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].cap=cc;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;
 16 }
 17 void addedge1(int bb,int ee,int cc,int vv)
 18 {
 19     addedge(bb,ee,cc,vv);addedge(ee,bb,0,-vv);
 20 }
 21 int xy(int x,int y){return (x-1)*c+y;}
 22 int SPFA()
 23 {
 24     int head,tail,i,u,v;
 25     head=0;tail=1;q[tail]=S;
 26     for(i=1;i<=T;i++)dis[i]=INF;dis[S]=0;
 27     memset(vis,false,sizeof(vis));vis[S]=true;
 28     while(head!=tail)
 29     {
 30         head++;if(head==610)head=0;
 31         u=q[head];
 32         for(i=Head[u];i!=-1;i=edge[i].next)
 33         {
 34             if(edge[i].cap>0)
 35             {
 36                 v=edge[i].end;
 37                 if(dis[u]+edge[i].value<dis[v])
 38                 {
 39                     dis[v]=dis[u]+edge[i].value;
 40                     from[v]=i;
 41                     if(vis[v]==false)
 42                     {
 43                         vis[v]=true;
 44                         tail++;if(tail==610)tail=0;
 45                         q[tail]=v;
 46                     }
 47                 }
 48             }
 49         }
 50         vis[u]=false;
 51     }
 52     if(dis[T]<INF)return 1;
 53     else return 0;
 54 }
 55 void MCF()
 56 {
 57     int F=INF,i;
 58     for(i=from[T];i;i=from[edge[i].begin])F=min(F,edge[i].cap);
 59     for(i=from[T];i;i=from[edge[i].begin]){edge[i].cap-=F,edge[i^1].cap+=F;ans+=F*edge[i].value;}
 60     //ans+=dis[T];
 61     memset(from,0,sizeof(from));
 62 }
 63 int main()
 64 {
 65     int r,i,j,k,XY,x1,y1;
 66     scanf("%d %d",&r,&c);
 67     for(i=1;i<=r;i++)
 68     {
 69         scanf("
%s",a[i]+1);
 70     }
 71     S=601;T=602;
 72     memset(Head,-1,sizeof(Head));cnt=1;
 73     for(i=1;i<=r;i++)
 74     {
 75         for(j=1;j<=c;j++)
 76         {
 77             XY=xy(i,j);
 78             addedge1(S,XY,1,0);
 79             addedge1(XY+300,T,1,0);
 80             for(k=0;k<=3;k++)
 81             {
 82                 x1=i+fx[k];
 83                 y1=j+fy[k];
 84                 if(x1<1)x1=r;if(x1>r)x1=1;
 85                 if(y1<1)y1=c;if(y1>c)y1=1;
 86                 if(a[i][j]=='U'&&k==3){addedge1(XY,xy(x1,y1)+300,1,0);continue;}
 87                 if(a[i][j]=='D'&&k==2){addedge1(XY,xy(x1,y1)+300,1,0);continue;}
 88                 if(a[i][j]=='L'&&k==1){addedge1(XY,xy(x1,y1)+300,1,0);continue;}
 89                 if(a[i][j]=='R'&&k==0){addedge1(XY,xy(x1,y1)+300,1,0);continue;}
 90                 addedge1(XY,xy(x1,y1)+300,1,1);
 91             }
 92             /*if(a[i][j]=='U')
 93             {
 94                 if(i-1>=1)addedge1(XY,xy(i-1,j)+300,1,0);
 95                 else addedge1(XY,xy(r,j)+300,1,0);
 96             }
 97             else if(a[i][j]=='D')
 98             {
 99                 if(i+1<=r)addedge1(XY,xy(i+1,j)+300,1,0);
100                 else addedge1(XY,xy(1,j)+300,1,0);
101             }
102             else if(a[i][j]=='L')
103             {
104                 if(j-1>=1)addedge1(XY,xy(i,j-1)+300,1,0);
105                 else addedge1(XY,xy(i,c)+300,1,0);
106             }
107             else
108             {
109                 if(j+1<=c)addedge1(XY,xy(i,j+1)+300,1,0);
110                 else addedge1(XY,xy(i,1)+300,1,0);
111             }*/
112         }
113     }
114     ans=0;
115     while(SPFA())MCF();
116     printf("%d",ans);
117     return 0;
118 }

View Code