2010年1月31日星期日.ural1067-pku1760
算是数据结构类的题吧。
其实不难只不过怪我不该不仔细读题，然后还看了pku上仅有的两个发言，
有一哥们说不是绝对路径，然后我就全理解错了。
看到
http://www.nocow.cn/index.php/URAL%E9%A2%98%E8%A7%A3
上有题解，不过是pascal的，努力看了看，才发现我理解错了。。。
其实题目的意思是
给出从根开始的文件夹名字，让你组建树结构
注意：如果给出两个路径
a\b
b\c
那么结果应该是
a
b
b
c
而不是
a
b
c
我一开始就是这么理解的，然后错了。。。
一个方法是按照树的遍历那么写，还有一个方法还可以对每个路径排序，然后递归输出。
还有就是要注意按照字典序输出。
还有就是pku和ural的编译器好像都不是很标准的g++
ural的是vc++ 7.0
pku的是MinGW,和vc++ 8.0
我是在linux下用g++-4.4写的，然后传上去之后两个地方全报编译错误。。。
都是string 的 <运算符重载问题。
1
2 #define pb(x) push_back(x)
3 const int N = 512 * 4;
4
5 int n;
6 bool getword(char s[N])
7 {//http://www.cppblog.com/schindlerlee
8 int i = 0;
9 char t;
10 //t = getchar();
11 scanf("%c", &t);
12 while (t != '\\' && t != '\n') {
13 s[i++] = t;
14 //t = getchar();
15 scanf("%c", &t);
16 }
17 s[i++] = 0;
18 return t == '\n';
19 }
20
21 struct L {
22 string s;
23 vector < L * >next;
24 } *root, pool[N * 10];
25 int sp, top;
26 string str[N];
27
28 bool cmp(L * a, L * b) { return strcmp((a->s).c_str() , (b->s).c_str()) < 0; }
29 void insert(L * root, int idx)
30 {
31 //printf("idx =%d\n",idx);
32 if (idx == sp) return;
33
34 int i, sz = root->next.size();
35 for (i = 0; i < sz; i++) {
36 if (!strcmp(root->next[i]->s.c_str() , str[idx].c_str())) {
37 return insert(root->next[i], idx + 1);
38 }
39 }
40 if (i == sz) {
41 pool[top].s = str[idx];
42 root->next.pb(&pool[top]);
43 insert(&pool[top++], idx + 1);
44 }
45 }
46
47 void dfs(L * root, int margin)
48 {
49 sort(root->next.begin(), root->next.end(), cmp);
50 int i, sz = root->next.size();
51 for (i = 0; i < sz; i++) {
52 int j = margin;
53 while (j--)
54 putchar(' ');
55 cout << (root->next[i]->s.c_str()) << endl;
56 dfs(root->next[i], margin + 1);
57 }
58 }
59
60 char s[N];
61 int main()
62 {
63 root = &pool[top++], root->s = "";
64 int i, j;
65 scanf("%d\n", &n);
66 for (i = 0; i < n; i++) {
67 sp = 0;
68 while (1) {
69 int isend = getword(s);
70 str[sp++] = s;
71 if (isend) break;
72 }
73 insert(root, 0);
74 }
75 dfs(root, 0);
76 return 0;
77 }
78