【作业】Kitchen Plates（拓扑排序）

题目链接：https://vjudge.net/contest/345791#problem/O

【问题描述】

　　You are given 5 different sizes of kitchen plates. Each plate is marked with a letter $A$

$A$

输入：

The input consist of 5 lines. In each line there will be 3 characters, the first and last character will be either $A$

$A$

样例输入;

D>B
A>D
E<C
A>B
B>C

B>E
A>B
E>A
C<B
D<B

样例输出：

ECBDA

impossible

试题分析：
　　给出5个大小关系，求其中一种满足从小到大的排列方式。因为输入并没有保证一定可以确定每两个Plate之间的大小关系，无法准确确定大小关系。题意只需要输出一种满足升序的排列即可，即用拓扑排序。
代码如下：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<queue>
 5 #include<string>
 6 #include<map>
 7 #define mem(a, b) memset(a, b, sizeof(a))
 8 const int MAXN = 10;
 9 using namespace std;
10 
11 char s[MAXN];
12 int in[MAXN], out[MAXN];
13 int head[MAXN], cnt;
14 map<char, int> mp;
15 map<int, char> mpp;
16 string ans;
17 
18 struct Edge
19 {
20     int to, next;
21 }edge[MAXN];
22 
23 void add(int a, int b)
24 {
25     cnt ++;
26     edge[cnt].to = b;
27     edge[cnt].next = head[a];
28     head[a] = cnt;
29 }
30 
31 void topo_sort()
32 {
33     queue<int> Q;
34     for(int i = 1; i <= 5; i ++)
35         if(!in[i])
36             Q.push(i);
37     while(!Q.empty())
38     {
39         int a = Q.front();
40         Q.pop();
41         ans += mpp[a];
42         for(int i = head[a]; i != -1; i = edge[i].next)
43         {
44             int to = edge[i].to;
45             in[to] --;
46             if(!in[to])
47             {
48                 Q.push(to);
49             }
50         }
51     }
52     if(ans.length() != 5)
53         printf("impossible
");
54     else
55         cout << ans << endl;
56 }
57 
58 int main()
59 {
60     mp['A'] = 1, mp['B'] = 2, mp['C'] = 3, mp['D'] = 4, mp['E'] = 5;
61     mpp[1] = 'A', mpp[2] = 'B', mpp[3] = 'C', mpp[4] = 'D', mpp[5] = 'E';
62     
63     mem(head, -1), cnt = 0;
64     ans = "";
65     for(int i = 1; i <= 5; i ++)
66     {
67         scanf("%s", s);
68         int x = mp[s[0]], y = mp[s[2]];
69         if(s[1] == '<')  //A < B则连边 表示A比B小 
70         {
71             add(x, y);
72             out[x] ++;
73             in[y] ++;
74         }
75         else
76         {
77             add(y, x);
78             out[y] ++;
79             in[x] ++;
80         }    
81     }
82     topo_sort();
83     return 0;
84 }

View Code