注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2346][Baltic 2011]Lamp  

2015-01-29 11:16:28|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2346: [Baltic 2011]Lamp

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 349  Solved: 150
[Submit][Status]

Description

2255是一个傻X,他连自己家灯不亮了都不知道。
某天TZ大神路过他家,发现了这一情况,
于是TZ开始行侠仗义了。
TZ发现是电路板的问题,
他打开了电路板,发现线路根本没有连上!!
于是他强大的脑力可以使某个格子上的线路从\变为/,
或者从/变为\。
2255不会电路(因为他什么都不会),但是他想知道TZ最少要用多少次脑力才能使他家的灯变亮。
如果无法变亮,输出“NO SOLUTION”。

n,m<=500

Sample Input

3 5
\\/\\
\\///
/\\\\

Sample Output

1

Solution

对于每条路,只有改跟不改两种情况,改会贡献1的代价,不改不贡献代价,也就是贡献0的代价,要求最小代价。这启发我们建图连边,将问题转化为我们所熟知的最短路问题。
原图中每个节点作为点,对于一个正方形中对角线相连的那两个点之间连一条代价为0的边,没有对角线相连的那两个点之间连一条代价为1的边,接下来只要做一遍最短路SPFA即可。
网格图卡SPFA是神器,所以要对SPFA进行一些优化。

我们知道,这张图的边权非0即1,那么我们就可以考虑双端队列,如果边权是0则加入队首,否则加入队尾。这样边权为0的就会优先搜索,对接下来搜索树的收缩非常有贡献。

其实还不如写dijkstra

Code

/**************************************************************
    Problem: 2346
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1836 ms
    Memory:128780 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
const int MAXN=2500010,MAXM=2500010;
int la[MAXN],et,d[MAXN],in[MAXN],hr,s,t;
struct E{int to,v,nxt;}e[MAXM<<1];
void add(int x,int y,int v)
{
    e[++et]=(E){y,v,la[x]};la[x]=et;
    e[++et]=(E){x,v,la[y]};la[y]=et;
}
struct H{int n,d;}h[MAXN<<1];
void insert(const H&t)
{
    int i;
    for(i=++hr;i!=1;i>>=1)if(t.d<h[i>>1].d)h[i]=h[i>>1];else break;
    h[i]=t;
}
void dlttop()
{
    hr--;int i;
    for(i=1;(i<<1)<=hr;)
    if(h[hr+1].d<=h[i<<1].d&&h[hr+1].d<=h[i<<1|1].d)break;
    else if(i<<1!=hr&&h[i<<1|1].d<h[i<<1].d)h[i]=h[i<<1|1],i=i<<1|1;
    else h[i]=h[i<<1],i=i<<1;
    h[i]=h[hr+1];
}
void dijkstra()
{
    memset(in,0,sizeof(in));
    memset(d,127,sizeof(d));int i;
    for(insert((H){s,d[s]=0});hr;dlttop())
    {
        if(in[h[1].n])continue;in[h[1].n]=1;
        for(i=la[h[1].n];i;i=e[i].nxt)
        if(d[e[i].to]>d[h[1].n]+e[i].v)
        {
            d[e[i].to]=d[h[1].n]+e[i].v;
            insert((H){e[i].to,d[e[i].to]});
        }
    }
}
int T,n,m,map[510][510];
int gp(int x,int y){return x*(m+1)+y+1;}
int main()
{
    scanf("%d%d",&n,&m);int i,j;
    for(i=1;i<=n;i++)
    {
        getchar();
        for(j=1;j<=m;j++)
        if(getchar()=='\\')
        {
            add(gp(i-1,j-1),gp(i,j),0);
            add(gp(i,j-1),gp(i-1,j),1);
        }
        else
        {
            add(gp(i-1,j-1),gp(i,j),1);
            add(gp(i,j-1),gp(i-1,j),0);    
        }
    }
    if((n+m)&1)return puts("NO SOLUTION"),0;
    s=1;t=(n+1)*(m+1);dijkstra();printf("%d\n",d[t]);
}
  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018