Time Limit: 3000 mSec
Problem Description
Input
The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of two lines. The first line contains an integer n (1 ≤ n ≤ 10), where n is the length of a sequence of integers. The second line contains a string of n(n + 1)/2 characters such that the first n characters correspond to the first row of the sign matrix, the next n−1 characters to the second row, ..., and the last character to the n-th row.
Output
For each test case, output exactly one line containing a sequence of n integers which generates the sign matrix. If more than one sequence generates the sign matrix, you may output any one of them. Every integer in the sequence must be between −10 and 10, both inclusive.
Sample Input
3 4 -+0++++--+ 2 +++ 5 ++0+-+-+--+-+-
Sample Output
-2 5 -3 1
3 4
1 2 -3 4 -5
题解：这个题联想到拓扑排序不容易（做题太少），不过有了这个大方向之后就很好办了，关于赋值的问题，给最开始入度为0的点随便赋个值，之后每一层的点的是上一层的值减一，最后把sum[0]要化为0， 因此每个数都减去sum[0]即可。
1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 #define REP(i, n) for (int i = 1; i <= (n); i++)
6 #define sqr(x) ((x) * (x))
7
8 const int maxn = 50 + 10;
9 const int maxm = 30 + 10;
10 const int maxs = 10000 + 10;
11
12 typedef long long LL;
13 typedef pair<int, int> pii;
14 typedef pair<double, double> pdd;
15
16 const LL unit = 1LL;
17 const int INF = 0x3f3f3f3f;
18 const LL mod = 1000000007;
19 const double eps = 1e-14;
20 const double inf = 1e15;
21 const double pi = acos(-1.0);
22
23 int n, deg[maxn];
24 vector<int> G[maxn];
25 int ans[maxn];
26
27 void toposort()
28 {
29 queue<int> que;
30 for (int i = 0; i <= n; i++)
31 {
32 if (!deg[i])
33 {
34 que.push(i);
35 ans[i] = 10;
36 }
37 }
38
39 while (!que.empty())
40 {
41 int head = que.front();
42 que.pop();
43 for (auto v : G[head])
44 {
45 deg[v]--;
46 if (!deg[v])
47 {
48 que.push(v);
49 ans[v] = ans[head] - 1;
50 }
51 }
52 }
53 }
54
55 int main()
56 {
57 ios::sync_with_stdio(false);
58 cin.tie(0);
59 freopen("input.txt", "r", stdin);
60 //freopen("output.txt", "w", stdout);
61 int T;
62 cin >> T;
63 while (T--)
64 {
65 cin >> n;
66 for (int i = 0; i <= n; i++)
67 {
68 G[i].clear();
69 deg[i] = ans[i] = 0;
70 }
71 string str;
72 cin >> str;
73 int pos = 0;
74 for (int i = 1; i <= n; i++)
75 {
76 for (int j = i; j <= n; j++)
77 {
78 if (str[pos] == '+')
79 {
80 G[j].push_back(i - 1);
81 deg[i - 1]++;
82 }
83 else if (str[pos] == '-')
84 {
85 G[i - 1].push_back(j);
86 deg[j]++;
87 }
88 pos++;
89 }
90 }
91 toposort();
92 for (int i = 1; i <= n; i++)
93 {
94 ans[i] -= ans[0];
95 }
96 ans[0] = 0;
97 for (int i = 1; i <= n; i++)
98 {
99 cout << ans[i] - ans[i - 1];
100 if (i != n)
101 {
102 cout << " ";
103 }
104 else
105 {
106 cout << endl;
107 }
108 }
109 }
110 return 0;
111 }