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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2375Cow Ski Area题解  

2014-03-26 19:57:17|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                   奶牛滑雪 
                                             BY   LGS
题目大意:给你一张N*M的矩阵,每个值代表这个地方的高度,滑雪可以由高的滑到低的或者相同的,且只能向相邻的4个方向滑。可以添加两个点的缆车,联通两个点,且是双向的。求使这张矩阵中的任意两个点联通的最小缆车数。

题解: 一开始想写强连通算法的,后来发现此题的特殊性,因为此题是有无向图和有向图结合的,且某个点联通的一定只有四个方向查找。所以可以用BFS来对无向图进行缩点(无向图的缩点就是找联通快,深搜、并差急均可)然后变成了有向图。然后对于那些有向图,由于只能从高度高度到低的,所以每个下降序列中的每个点一定都是一个强连通分量。  现在就是运用贪心的结论:需要添加的边数一定是所有点中入度为0的点的个数和出度为0的点的个数的最大值。

总结:强连通分量的缩点

代码:
  • Source Code
  • #include<cstdio>
    #define maxn 600
    using namespace std;
    int ww,i,j,t,h,n,m,w,l,k,q,p,ans,anss;
    int a[maxn][maxn],que[maxn*maxn][2],
        color[maxn][maxn];
    bool b[maxn][maxn],chu[maxn*maxn],ru[maxn*maxn];
    const int han[4]={1,-1,0,0};
    const int lie[4]={0,0,1,-1};
    int main()
    {
     scanf("%d%d",&ww,&l);n=0;
     for (i=1;i<=l;i++) 
      for (j=1;j<=ww;j++)
                    scanf("%d",&a[i][j]);
                    
    for (i=1;i<=l;i++)
     for (j=1;j<=ww;j++)if (!color[i][j])
            {
            n++;
            t=0;w=1;que[1][0]=i;que[1][1]=j;b[i][j]=true;
            while (t<w){
                       t++;color[que[t][0]][que[t][1]]=n;
             for (k=0;k<=3;k++){
                            int x=que[t][0]+han[k],y=que[t][1]+lie[k];
                           if ((x>0)&&(x<=l)&&(y>0)&&(y<=ww))
             if ((!b[x][y])&&(a[que[t][0]][que[t][1]]==a[x][y])){
                                                                  w++;
                                                                 que[w][0]=x;
                                                                 que[w][1]=y;
                                                                 b[x][y]=true;  
                                                                   }  
                                }
                       }
          }
    for (i=1;i<=l;i++)
     for (j=1;j<=ww;j++) if (!color[i][j]) {n++;color[i][j]=n;}
    if (n==1){printf("0\n");return 0;}
    for (i=1;i<=l;i++)
     for (j=1;j<=ww;j++)
                        {
         for (k=0;k<=3;k++) {
                           int x=i+han[k],y=j+lie[k];
                           if ((x>0)&&(x<=l)&&(y>0)&&(y<=ww))
                            if (color[i][j]!=color[x][y])
                              if (a[i][j]>a[x][y]) {chu[color[i][j]]=true;
                                                     ru[color[x][y]]=true;
                                                   }
                            }
                        }
    ans=anss=0;
    for (i=1;i<=n;i++) {if (!chu[i])ans++;if (!ru[i])anss++;}
    if (ans>anss) printf("%d\n",ans);
     else printf("%d\n",anss);  
    return 0;                                 
    }
  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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