好像在本版看过这个题 、看到分就来了

收到的鲜花

• 有容就大 于 2012-08-17 17:13 送鲜花  10朵   附言：可以试下 呵呵

我来试一下。

收到的鲜花

• 有容就大 于 2012-08-17 17:14 送鲜花  10朵   附言：非常欢迎

确实没图也一样。看题意就是上面是水，下面是沙漠。

回头我有空也试试这个题。先 mark 一下，将来好和杨大哥学习。

不会做。我的 ACM 水平非常菜。
如果只是问能不能惠泽每个沙漠城市的话，那就是非常简单的一道题。但它还问了至少要几个蓄水厂，我不会做这种优化的题目。

我只能说下目前我的想法，抛砖引玉吧。假如输入是：
假设在每行内城市的编号是 1, 2, ...
目前比较朴素的想法是：很容易根据高低关系求出在所有蓄水厂能够惠泽的沙漠城市。
比如在 1 (第一行第一个城市，高为8) 这个城市修水站，能惠泽 1, 2 这两个沙漠城市 (最后一行第一和第二个城市，高度是3, 2)。记作 1: {1, 2}，那么就有
1: {1, 2}
2: {2}
3: {2, 3, 4}
4: {2, 3, 4, 5}
5: {5}
6: {6}
得到这个结果不难。最笨的方法复杂度也就是 O(MMN)。如果有不能惠泽的城市，到这还能回答出哪几个城市不能惠泽。

如果能惠泽全，还得想怎么用最少的水站。其实就是如何用最少的点并出全集。有子集关系的点很容易合并(其实第一步求的时候就能合并不少了)，但我依然不会选点。
感觉以前看杨大哥的代码里，有能干类似事的。但我其实对广搜很不在行，悟性也比较低。

收到的鲜花

• 有容就大 于 2012-08-17 17:16 送鲜花  10朵   附言：恩 这个实际向理论的建模很有意思 期待P版 ...

我只是一个菜鸟，从未做过acm的题（其实没有这个贴我不知道acm是什么。），来这里发帖只是蹭分的，好不容易写了一个代码，但准备发帖是看见楼上大神的贴后瞬间觉得我不仅优化得不是很成功，而且用的方法也是很笨的，本来不想发帖的，但一想就算我代码写得再差，大神们也会好心指导我，而且也不知道我是谁，不用太丢脸，就还是发了，代码如下，请大神多指点。

#include<stdio.h>
#include<malloc.h>
void xiu(struct node*,int,int *,struct node *);
struct node

 {
     int num;
     struct node *p[3];

 };
int main()
{

 int n,m;

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

 struct node **p1=(struct node **)malloc(sizeof(struct node *)*m);

 p1[0]=(struct node *)malloc(sizeof(struct node)*m*n);

 for(int y=1;y<m;y++)
     p1[y]=p1[y-1]+n;

 for(int i=0;i<m;i++)
{    
    for(int j=0;j<n;j++)
        {
            scanf("%d",&p1[i][j].num);
            for(int l=0;l<3;l++)
                p1[i][j].p[l]=NULL;
        }
}
for(int k=0;k<m;k++)    

 {
    for(int j=0;j<n;j++)
    {int i=0;
    if(k!=0)
        if(p1[k][j].num>p1[k-1][j].num)
            p1[k][j].p[i++]=&p1[k-1][j];
    if(k!=m-1)
        if(p1[k][j].num>p1[k+1][j].num)
            p1[k][j].p[i++]=&p1[k+1][j];
    if(j!=n-1)
        if(p1[k][j].num>p1[k][j+1].num)
            p1[k][j].p[i++]=&p1[k][j+1];
    if(j!=0)
        if(p1[k][j].num>p1[k][j-1].num)
            p1[k][j].p[i]=&p1[k][j-1];
    }

 }

 int *start=(int *)malloc(sizeof(int)*n);

 start[0]=0;

 struct node *p2;

 for(int j=1;j<n;j++)
    if(p1[0][start[0]].num<p1[0][j].num)
        start[0]=j;

 for(int s=1;s<n;s++)
    {
            start[s]=s;
        for(int j=1;j<n;j++)
        if(p1[0][start[s]].num<p1[0][j].num && p1[0][j].num<=p1[0][start[s-1]].num)
            start[s]=j;
    }
int *end=(int *)malloc(sizeof(int)*n);
for(s=0;s<n;s++)
end[s]=0;
for(s=0;s<n;s++)

 {    p2=&p1[0][start[s]];
    xiu(p2,(m-1)*n,end,p1[0]);
    for(int i=0;;i++)
    {
        if(end[i]==0)
        break;
     if(i==m-1)
     {
         printf("\n  1 \n %d",s+1);
             return 0;
     }
    
    
    }
    

 }


 int c=0;

 for(int o=0;o<n;o++)

 {
    if(end[o]==0)
        c++;
    

 }

 printf("\n  0 \n  %d",c);

 

 return 0;

 }
void xiu(struct node *lp,int n,int *end,struct node *p1)
{if((lp-p1)>=n)
end[lp-p1-n]=1;
if(lp->p[0]!=NULL)
xiu(lp->p[0],n,end,p1);
if(lp->p[1]!=NULL)
xiu(lp->p[1],n,end,p1);
if(lp->p[2]!=NULL)
xiu(lp->p[2],n,end,p1);
}

再说一下优化问题：我觉得在每个城市都能行的情况下，先一个城市一个城市的试，行的话输出1，不行的话2个城市2个城市的试，行的话输出2，不行就3个城市一起试，依次类推，直到数量达到最大值，这个方法比较笨，但应该可用，但太费时间了。

收到的鲜花

• 有容就大 于 2012-08-17 19:14 送鲜花  10朵   附言：好文章

这位朋友 很不错
其实我也只能大概知道个解题的流程 但是在把实际问题向代码转化的过程中卡壳了
还没有完整的代码 即使是像你自己说自己比较笨的那种办法 至少你这种态度就是非常好的
别说一个难的问题 即使一个比较容易的问题 能通过自己的思路转化为代码都是值得称赞的。

看了下你的代码 这句有点问题： for(s=0;s<n;s++) 这里的s没有定义 也就是不能使用上面只具有语句作用域的s，
可以再检查一遍， 还有就是提醒下 你的代码排版可以改进下 呵呵 几乎每句都是从第一列开始出发的，有些适当的缩进或者注释 可以让代码变得清晰 别人在阅读你的代码时会感觉很轻松 你的思路展现的就更加充分 大家交流起来也就更顺畅了。呵呵 一点建议啊。

呵呵 看了下杨大哥给的杭电的竞赛题 引水入城这个还没人AC呢 大家加油啊 为BCCN争光！

有趣，关注...

如果输入的数据是：
2 5
9 1 6 3 3
8 1 5 1 2
结果是什么呢？

有点象扫雷！

收到的鲜花

• 有容就大 于 2012-08-17 23:18 送鲜花  10朵   附言：呵呵 是有点像