「BZOJ3171」[TJOI2013] 循环格

2014年3月18日4,5180

Description

Input

第一行两个整数R，C。表示行和列，接下来R行，每行C个字符LRUD，表示左右上下。

Output

一个整数，表示最少需要修改多少个元素使得给定的循环格完美

Sample Input

3 4
RRRD
URLL
LRRR

Sample Output

HINT

1<=R,L<=15

题解

可知每个点的出度=入度=1

二分图+费用流

S向每个点连容量1费用0的边

每个点拆出的点向T连容量1，费用0的边

每个格子向四周连费用0或1的边

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
#define T 600
using namespace std;
int n,m,cnt=1,ans;
int mp[16][16],mark[16][16],xx[4]={0,0,-1,1},yy[4]={-1,1,0,0};
int from[601],head[601],q[601],dis[601];
bool inq[601];
struct data{int to,from,next,v,c;}e[1000001];
void ins(int u,int v,int w,int c)
{
     e[++cnt].to=v;e[cnt].from=u;
     e[cnt].next=head[u];head[u]=cnt;
     e[cnt].v=w;e[cnt].c=c;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);}
void build()
{
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<4;k++)
            {
                int nowx=i+xx[k],nowy=j+yy[k];
                if(nowx>n)nowx=1;if(nowx<1)nowx=n;
                if(nowy>m)nowy=1;if(nowy<1)nowy=m;
                if(k==mp[i][j])
                   insert(mark[i][j],mark[nowx][nowy]+300,1,0);
                else insert(mark[i][j],mark[nowx][nowy]+300,1,1);
                }
     for(int i=1;i<=n*m;i++)
     {insert(0,i,1,0);insert(i+300,T,1,0);}
     }
bool spfa()
{
	 for(int i=0;i<=T;i++)dis[i]=inf;
    int t=0,w=1,i,now;
    dis[0]=0;inq[0]=1;q[0]=0;
    while(t!=w)
    {
        now=q[t];t++;if(t==601)t=0;
        for(i=head[now];i;i=e[i].next)
        {
                if(e[i].v&&e[i].c+dis[now]<dis[e[i].to])
                {
                    dis[e[i].to]=e[i].c+dis[now];
                    from[e[i].to]=i;
                    if(!inq[e[i].to])
                    {
                        inq[e[i].to]=1;
                        q[w++]=e[i].to;
                        if(w==601)w=0; 
                                     }
                }
        }
        inq[now]=0;
    }
    if(dis[T]==inf)return 0;return 1;
}
void mcf()
{
    int x=inf;
    for(int i=from[T];i;i=from[e[i].from])
    {
        x=min(e[i].v,x);
    }
    for(int i=from[T];i;i=from[e[i].from])
    {
        e[i].v-=x;e[i^1].v+=x;
        ans+=x*e[i].c;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
          mark[i][j]=(i-1)*m+j;
    for(int i=1;i<=n;i++)
    {
       char ch[21];scanf("%s",ch);
       for(int j=1;j<=m;j++)
       {
          if(ch[j-1]=='L')mp[i][j]=0;
          if(ch[j-1]=='R')mp[i][j]=1;
          if(ch[j-1]=='U')mp[i][j]=2;
          if(ch[j-1]=='D')mp[i][j]=3;
          }
       }
    build();
    while(spfa())mcf();
    printf("%d",ans);
    return 0;
 }

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 0x7fffffff

#define T 600

using namespace std;

int n,m,cnt=1,ans;

int mp[16][16],mark[16][16],xx[4]={0,0,-1,1},yy[4]={-1,1,0,0};

int from[601],head[601],q[601],dis[601];

bool inq[601];

struct data{int to,from,next,v,c;}e[1000001];

void ins(int u,int v,int w,int c)

{

e[++cnt].to=v;e[cnt].from=u;

e[cnt].next=head[u];head[u]=cnt;

e[cnt].v=w;e[cnt].c=c;

}

void insert(int u,int v,int w,int c)

{ins(u,v,w,c);ins(v,u,0,-c);}

void build()

{

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

for(int k=0;k<4;k++)

{

int nowx=i+xx[k],nowy=j+yy[k];

if(nowx>n)nowx=1;if(nowx<1)nowx=n;

if(nowy>m)nowy=1;if(nowy<1)nowy=m;

if(k==mp[i][j])

insert(mark[i][j],mark[nowx][nowy]+300,1,0);

else insert(mark[i][j],mark[nowx][nowy]+300,1,1);

}

for(int i=1;i<=n*m;i++)

{insert(0,i,1,0);insert(i+300,T,1,0);}

}

bool spfa()

{

for(int i=0;i<=T;i++)dis[i]=inf;

int t=0,w=1,i,now;

dis[0]=0;inq[0]=1;q[0]=0;

while(t!=w)

{

now=q[t];t++;if(t==601)t=0;

for(i=head[now];i;i=e[i].next)

{

if(e[i].v&&e[i].c+dis[now]<dis[e[i].to])

{

dis[e[i].to]=e[i].c+dis[now];

from[e[i].to]=i;

if(!inq[e[i].to])

{

inq[e[i].to]=1;

q[w++]=e[i].to;

if(w==601)w=0;

}

inq[now]=0;

}

if(dis[T]==inf)return 0;return 1;

}

void mcf()

{

int x=inf;

for(int i=from[T];i;i=from[e[i].from])

{

x=min(e[i].v,x);

}

for(int i=from[T];i;i=from[e[i].from])

{

e[i].v-=x;e[i^1].v+=x;

ans+=x*e[i].c;

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

mark[i][j]=(i-1)*m+j;

for(int i=1;i<=n;i++)

{

char ch[21];scanf("%s",ch);

for(int j=1;j<=m;j++)

{

if(ch[j-1]=='L')mp[i][j]=0;

if(ch[j-1]=='R')mp[i][j]=1;

if(ch[j-1]=='U')mp[i][j]=2;

if(ch[j-1]=='D')mp[i][j]=3;

}

build();

while(spfa())mcf();

printf("%d",ans);

return 0;

}

« 「BZOJ2424」[HAOI2010] 订货「网络流24题」航空计划 »

hzwer.com _ Home | http://hzwer.com

「BZOJ3171」[TJOI2013] 循环格

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论