本文共 1454 字，大约阅读时间需要 4 分钟。
题目传送：
白书例题
注意拓扑排序时，，入度同一时候为0的前缀和须要赋值为同一个数（这个数能够随机取。由于前缀和是累加的，每个a的数值都仅仅和前缀和之差有关）。，由于此时能够看成他们的前缀和是相等的，不存在大小关系，，而存在大小关系的都连了一条有向边。
。假设此时不赋值为同一个数，，可能对于符号0不是正解。，从而产生错误的结果。。
AC代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define INF 0x7fffffffusing namespace std;int n;char str[1005];int indeg[35];int vis[35];int mp[35][35];int prefix[35];void toposort() { int d = 0, c = 0; while(d <= n) { memset(vis, 0, sizeof(vis)); for(int i = 0; i <= n; i ++) { if(indeg[i] == 0) { prefix[i] = c; indeg[i] = -1; vis[i] = 1; d ++; } } c ++; for(int i = 0; i <= n; i ++) { if(vis[i]) { for(int j = 0; j <= n; j ++) { if(mp[i][j] == 1) { indeg[j] --; } } } } }}int main() { int T; scanf("%d", &T); while(T --) { scanf("%d", &n); scanf("%s", str); memset(indeg, 0, sizeof(indeg)); memset(mp, 0, sizeof(mp)); int c = 0; for(int i = 1; i <= n; i ++) { for(int j = i; j <= n; j ++) { if(str[c] == '+') { mp[i - 1][j] = 1; indeg[j] ++; } else if(str[c] == '-') { mp[j][i - 1] = 1; indeg[i - 1] ++; } c ++; } } toposort(); //for(int i = 0; i <= n; i ++) cout << prefix[i] << " "; cout << endl; for(int i = 1; i < n; i ++) { printf("%d ", prefix[i] - prefix[i - 1]); } printf("%d\n", prefix[n] - prefix[n - 1]); } return 0;}
转载地址：http://cylpa.baihongyu.com/