鱼C论坛

 找回密码
 立即注册
查看: 3000|回复: 3

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

[复制链接]
发表于 2014-4-16 14:03:59 | 显示全部楼层 |阅读模式
20鱼币
这是题目传送门:
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1004
我的代码是:
  1. #include <iostream>
  2. using namespace std;

  3. bool DFS(bool station[150][150],int posx,int posy,int end,bool column[101],int max);

  4. int main()
  5. {
  6.         int T;        //0<T<30
  7.         int start,end;        //[0,100]
  8.         int n;                //0<n<=50

  9.         cin>>T;
  10.         for (int i=0;i<T;i++)
  11.         {
  12.                 int max=-1;
  13.                 bool station[150][150]={{false}};        //邻接矩阵
  14.                 bool column[150]={false};                //记录某列是否已经走过
  15.                 cin>>start>>end>>n;
  16.                 int temp,before;
  17.                 while (1)
  18.                 {
  19.                         if ('\n' == cin.peek())
  20.                         {
  21.                                 before=-1;
  22.                                 if (0 == n--)        break;
  23.                         }
  24.                         cin>>temp;
  25.                         if (temp > max)        max=temp;
  26.                         if (-1 == before)        before=temp;
  27.                         else if (temp == before)        continue;
  28.                         else        station[temp][before]=station[before][temp]=true;
  29.                 }
  30.                 if (DFS(station,start,0,end,column,max))        cout<<"Yes"<<endl;
  31.                 else        cout<<"No"<<endl;
  32.         }
  33.         return 0;
  34. }

  35. bool DFS(bool station[150][150],int posx,int posy,int end,bool column[101],int max)
  36. {
  37.         if (posy == end && true == station[posx][end])
  38.                 return true;
  39.         else if (posy > max)
  40.                 return false;

  41.         if (true == station[posx][posy] && false == column[posy])
  42.         {
  43.                 column[posy]=true;
  44.                 if (DFS(station,posy,0,end,column,max))        return true;
  45.                 column[posy]=false;
  46.         }
  47.         return DFS(station,posx,posy+1,end,column,max);
  48. }
复制代码
系统说我执行时间超过了1s,是不是DFS在此不适用?:mad:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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
  1. #include <cstdio>
  2. #include <iostream>
  3. using namespace std;
  4. int rank[1000000];
  5. int p[1000000];

  6. void makeset(int x){
  7.         p[x]=x;
  8.         rank[x]=0;
  9. }

  10. int findp(int x){
  11.           if (p[x] != x)p[x]=findp(p[x]);
  12.           
  13.           return p[x];
  14. }

  15. void unionset(int x, int y){
  16.         int xp,yp;
  17.         xp=findp(x);
  18.         yp=findp(y);
  19.         if (xp==yp)return;
  20.        
  21.         if (rank[xp]<rank[yp])p[xp]=yp;
  22.         else if (rank[xp]>rank[yp])p[yp]=xp;
  23.         else  { //if equal
  24.                 p[yp]=xp;     
  25.                 rank[xp]++;
  26.         }
  27. }


  28. int main()
  29. {
  30.         bool firstc=true;
  31.         int t,n,x,s,e,i=0;
  32.         int temp;
  33.         scanf ("%d",&t);
  34.         while (t--){
  35.                 scanf("%d%d",&s,&e);
  36.                 scanf("%d",&n);
  37.                 while (n--){
  38.                         if (firstc)scanf("%d",&temp); //skip first c
  39.                         int x1;
  40.                         while (1){
  41.                                 if (cin.peek()=='\n')break;
  42.                                 if (i!=0)x1=x;
  43.                                 scanf("%d",&x);
  44.                                 makeset(x);
  45.                                 if (i!=0){
  46.                                         unionset(x,x1);
  47.                                 }
  48.                                 i++;
  49.                         }
  50.                         firstc=true;
  51.                 }
  52.                 if (findp(s)==findp(e))printf("Yes\n");
  53.                 else printf("No\n");
  54.                
  55.         }
  56.        
  57.        
  58.         return 0;
  59. }
复制代码
你可以拿去试试,反正他给的Test case都过关了。还有就是你应该学会用cstdio中的scanf()和printf()。这两个比Cin和cout要快很多,有的时候他给的数据庞大了,时间差距就十分明显了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2014-4-19 02:02:58 | 显示全部楼层

你的也是Time Limit:titter:
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-4-19 10:31:27 | 显示全部楼层
这。。。我也不清楚了。。学艺不精啊。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 13:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表