cuibaowenown2 发表于 2014-4-16 14:03:59

ACM的一道题，我用DFS（深度优先遍历）结果被判定时间过长，是我写错了还是DFS不适合

这是题目传送门：
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1004
我的代码是：
#include <iostream>
using namespace std;

bool DFS(bool station,int posx,int posy,int end,bool column,int max);

int main()
{
        int T;        //0<T<30
        int start,end;        //
        int n;                //0<n<=50

        cin>>T;
        for (int i=0;i<T;i++)
        {
                int max=-1;
                bool station={{false}};        //邻接矩阵
                bool column={false};                //记录某列是否已经走过
                cin>>start>>end>>n;
                int temp,before;
                while (1)
                {
                        if ('\n' == cin.peek())
                        {
                                before=-1;
                                if (0 == n--)        break;
                        }
                        cin>>temp;
                        if (temp > max)        max=temp;
                        if (-1 == before)        before=temp;
                        else if (temp == before)        continue;
                        else        station=station=true;
                }
                if (DFS(station,start,0,end,column,max))        cout<<"Yes"<<endl;
                else        cout<<"No"<<endl;
        }
        return 0;
}

bool DFS(bool station,int posx,int posy,int end,bool column,int max)
{
        if (posy == end && true == station)
                return true;
        else if (posy > max)
                return false;

        if (true == station && false == column)
        {
                column=true;
                if (DFS(station,posy,0,end,column,max))        return true;
                column=false;
        }
        return DFS(station,posx,posy+1,end,column,max);
}系统说我执行时间超过了1s，是不是DFS在此不适用？:mad:

rockerz 发表于 2014-4-18 10:54:55

本帖最后由 rockerz 于 2014-4-18 11:31 编辑

这道题只给你1s的时间但给了你128mb的内存，明显是要你用内存来换时间。用并查表会快很多。union find disjoint set。
http://zh.wikipedia.org/zh-sg/%E5%B9%B6%E6%9F%A5%E9%9B%86
#include <cstdio>
#include <iostream>
using namespace std;
int rank;
int p;

void makeset(int x){
        p=x;
        rank=0;
}

int findp(int x){
          if (p != x)p=findp(p);
          
          return p;
}

void unionset(int x, int y){
        int xp,yp;
        xp=findp(x);
        yp=findp(y);
        if (xp==yp)return;
       
        if (rank<rank)p=yp;
        else if (rank>rank)p=xp;
        else{ //if equal
                p=xp;   
                rank++;
        }
}


int main()
{
        bool firstc=true;
        int t,n,x,s,e,i=0;
        int temp;
        scanf ("%d",&t);
        while (t--){
                scanf("%d%d",&s,&e);
                scanf("%d",&n);
                while (n--){
                        if (firstc)scanf("%d",&temp); //skip first c
                        int x1;
                        while (1){
                                if (cin.peek()=='\n')break;
                                if (i!=0)x1=x;
                                scanf("%d",&x);
                                makeset(x);
                                if (i!=0){
                                        unionset(x,x1);
                                }
                                i++;
                        }
                        firstc=true;
                }
                if (findp(s)==findp(e))printf("Yes\n");
                else printf("No\n");
               
        }
       
       
        return 0;
}
你可以拿去试试，反正他给的Test case都过关了。还有就是你应该学会用cstdio中的scanf()和printf()。这两个比Cin和cout要快很多，有的时候他给的数据庞大了，时间差距就十分明显了。

cuibaowenown2 发表于 2014-4-19 02:02:58

rockerz 发表于 2014-4-18 10:54 static/image/common/back.gif
这道题只给你1s的时间但给了你128mb的内存，明显是要你用内存来换时间。用并查表会快很多。union find disj ...

你的也是Time Limit:titter:

rockerz 发表于 2014-4-19 10:31:27

这。。。我也不清楚了。。学艺不精啊。。
页: [1]
查看完整版本: ACM的一道题，我用DFS（深度优先遍历）结果被判定时间过长，是我写错了还是DFS不适合