【深度优先搜索】MZOJ

【深度优先搜索】MZOJ_1344工作依赖

这道题的读入非常毒瘤。。。恶心到我了

我痛苦地弄了很久，还是被卡住了我还真是▇了狗了。[传送门](特此声明：学校内部OJ，需登录)

题目描述(Description):

2008年，奥运会将在中国举行。众所周知举办奥运会是一个庞大的工程，有许多准备工作要做，而这些工作也是要分先后、存在依赖关系的。比如我们说工作2依赖于工作1，意思是说在工作2开始做之前要必须结束工作1。我们假设，在一个时刻只有一个工作在进行，而且每样工作所依赖的其它工作不会超过10个。

输入文件(job.in):

第一行有两个整数N（0<=N<=10000）和M。所有工作从1到N编号。你需要计算第M个工作的最早结束时间。

接下来N行每行描述一个工作，第1行描述工作1，第二行描述工作2，……，以此类推。每行包含几个正整数，第i行的第1个整数是完成第i个工作需要的时间T（0<T<=100），第i行的其余数字是第i个工作所依赖的其它工作编号。我们保证不会出现循环依赖。

输出文件(job.out):

一个整数：工作M的最早结束时间。

样例(Sample):

Sample Input Case 1:

2 2

2 1

Sample Output Case 1:

Sample Input Case 2:

3 3

2 1

4 1 2

Sample Output Case 2:

这一道题是没有太大的思维难度的，只需要两个东西：1.建立好关系 2.读入！！！

有的dalao是用的BFS做的，这里是他的文章（应该是个学长吧，不认识。。）[你点我呀_(:3 」∠)_]

然而作为一个蒟蒻我觉得BFS太难推了，就果断选择了DFS。。

DFS的思路很简单：

首先我们需要存边。但是我们大部分人都会第一眼可能都是这样的:

若u依赖于v，则应建立一条v到u的有向边。

其实这样存边也可以，但是非常麻烦。因为我们要维护出m节点入边个数。我绝对不会告诉你我考试这样想了半个小时

那如果反向思考呢？如果我们建立一条从u到v的有向边。为什么这样更好？因为图的遍历在正常情况下所有以自己为起点的边总会遍历完。完全不需要考虑其他东西。

如果你硬是要按照黄字来建我又有什么办法,jpg

存图的思路若是建立好，开始遍历就很简单。

如果访问过的节点就不再访问。

先上一波伪代码：

1 DFS(cur)
2  {
3      ans+=t[cur];
4      cur is visted;
5      for(each edge (cur,v) from cur)
6 　　if(v is not visted)
7       DFS(v);
8 }

想必诸位看到了递归的好处了:简洁又很有说服力。

但是。。。其实我最主要死在了读入上面。。。。。

出这个毒瘤读入的老师开心地笑了

我先放几波死了的读入（电视机前的小朋友们请勿模仿）

死亡读入1：

 1 scanf("%d%d",&n,&m);
 2     for(int i=1;i<=n;++i)
 3     {
 4         int a=0;
 5         scanf("%d",t+i);
 6         while(scanf("%d",&a)==1)
 7         {
 8             g[i].push_back(a);
 9         }
10         else continue;
11     }

死亡读入2：

 1 scanf("%d%d",&n,&m);
 2     for(int i=1;i<=n;++i)
 3     {
 4         int a=0;
 5         scanf("%d",t+i);
 6         if(char ch=getchar()!='
')
 7         while(scanf("%d",&a)==1)
 8         {
 9             g[i].push_back(a);
10         }
11         else continue;
12     }

......(不一一枚举了)

读入虐我千百遍我待读入如初恋

又尤其是Dev-cpp这个东西它在调试的时候死活不给我往下走(经验实是因为Dev对STL容器兼容性不好，然而我用了vector)，我Alt+N都要按烂了。搞的我每次调的时候都要注释，再看看输入正确没有。

我百思不得其解时，看到了大佬的代码，大佬是在读入时读入的字符串，再作计算。

我就借助这个思路同样用字符串去读，就完全OK。

（这是我第一次用vector，原因是我觉得不存边权的边用vector写起来舒服）

下附AC代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<vector>
 5 #define MAXN 10000+5
 6 using namespace std;
 7 //---------------
 8 vector<int>g[MAXN];
 9 typedef char String[100];
10 int n,m;
11 int ans=0;
12 bool vis[MAXN];
13 int t[MAXN];
14 void dfs(int cur)
15 {
16     //cout<<"当前节点："<<cur<<endl; 
17     ans+=t[cur];
18     //cout<<"ans="<<ans<<endl;
19     vis[cur]=true;
20     for(int i=0;i<g[cur].size();++i)
21     {
22         int v=g[cur][i];
23         if(!vis[v])/*cout<<"到v节点"<<v<<endl,*/dfs(v);//如果没有走 则一定要走他 
24     }
25 }
26 String s;
27 int main()
28 {
29     int a;
30     //freopen("input.txt","r",stdin);
31         scanf("%d%d",&n,&m);
32     for(int i=1;i<=n;++i)
33     {
34         a=0;
35         scanf("%d",t+i);
36         char ch=getchar();
37         if(ch=='
') continue;
38         else{
39             gets(s);
40             int LEN=strlen(s);
41             for(int j=0;j<LEN;++j)
42             {
43                 if(s[j]>='0' && s[j]<='9'){a=a*10+s[j]-'0';}
44                 if(s[j]==' ' || s[j+1]==''){g[i].push_back(a);a=0;}
45             }
46         } 
47     }
48     dfs(m);
49     printf("%d
",ans);
50     return 0;
51 }

所以后排%%%大佬们~