首页 > 代码库 > BZOJ3171: [Tjoi2013]循环格

BZOJ3171: [Tjoi2013]循环格

题解:

从一个点出发回到这个点?

那我们就把每个点拆成两个点i,i’

开始连边 s 到 i’,i 到 t。

相邻的连边 j‘ 到 i,费用等于方向改变的话就是1,否则为0。

然后跑费用流就可以了。

代码:

技术分享
  1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 200000+5 26  27 #define maxm 200000+5 28  29 #define eps 1e-10 30  31 #define ll long long 32  33 #define pa pair<int,int> 34  35 #define for0(i,n) for(int i=0;i<=(n);i++) 36  37 #define for1(i,n) for(int i=1;i<=(n);i++) 38  39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40  41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42  43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) 44  45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) 46  47 #define mod 1000000007 48  49 using namespace std; 50  51 inline int read() 52  53 { 54  55     int x=0,f=1;char ch=getchar(); 56  57     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();} 58  59     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();} 60  61     return x*f; 62  63 } 64 int n,m,k,mincost,tot=1,s,t,a[20][20],b[20][20][2],head[maxn],d[maxn],from[2*maxm]; 65  66 bool v[maxn]; 67  68 queue<int>q; 69  70 struct edge{int from,go,next,v,c;}e[2*maxm]; 71  72 void add(int x,int y,int v,int c) 73  74 { 75  76     e[++tot]=(edge){x,y,head[x],v,c};head[x]=tot; 77  78     e[++tot]=(edge){y,x,head[y],0,-c};head[y]=tot; 79  80 } 81  82 bool spfa() 83  84 { 85  86     for (int i=0;i<=t;i++){v[i]=0;d[i]=inf;} 87  88     q.push(s);d[s]=0;v[s]=1; 89  90     while(!q.empty()) 91  92     { 93  94         int x=q.front();q.pop();v[x]=0; 95  96         for (int i=head[x],y;i;i=e[i].next) 97  98          if(e[i].v&&d[x]+e[i].c<d[y=e[i].go]) 99 100          {101 102             d[y]=d[x]+e[i].c;from[y]=i;103 104             if(!v[y]){v[y]=1;q.push(y);}105 106          }107 108     }109 110     return d[t]!=inf;111 112 }113 const int dx[4]={0,0,-1,1};114 const int dy[4]={-1,1,0,0};115 inline int id(char ch)116 {117     if(ch==L)return 0;118     if(ch==R)return 1;119     if(ch==U)return 2;120     if(ch==D)return 3;121     return -1;122 }123 124 void mcf()125 126 {127 128     mincost=0;129 130     while(spfa())131 132     {133 134         int tmp=inf;135 136         for(int i=from[t];i;i=from[e[i].from]) tmp=min(tmp,e[i].v);137 138         mincost+=d[t]*tmp;139 140         for(int i=from[t];i;i=from[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;}141 142     }143 144 }145 int main()146 147 {148 149     freopen("input.txt","r",stdin);150 151     freopen("output.txt","w",stdout);152 153     n=read();m=read();s=2*n*m;t=s+1;154     for0(i,n-1)for0(j,m-1)155     {156         char ch=getchar();157         while(id(ch)==-1)ch=getchar();158         a[i][j]=id(ch);159         b[i][j][0]=i*m+j;b[i][j][1]=b[i][j][0]+n*m;160         add(s,b[i][j][1],1,0);add(b[i][j][0],t,1,0);161     }162     for0(i,n-1)for0(j,m-1)for0(k,3)163     {164         int x=(i+dx[k]+n)%n,y=(j+dy[k]+m)%m;165         if(x<0||x>=n||y<0||y>=m)continue;166         add(b[i][j][1],b[x][y][0],1,a[i][j]!=k);167     }168     mcf();169     cout<<mincost<<endl;170 171     return 0;172 173 }  
View Code

3171: [Tjoi2013]循环格

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 499  Solved: 287
[Submit][Status]

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

BZOJ3171: [Tjoi2013]循环格