程序员人生 网站导航

UVALive4255-Guess(拓扑排序)

栏目:互联网时间:2014-10-13 10:57:14

题目链接


题意:对于一个序列a1,a2...an,我们可以计算出一个符号矩阵S,其中Sij为ai+..+aj的正负号。给出符号矩阵,要求输出一个对应的序列。

思路:使用连续和转化为前缀和之差的技巧,将前缀和当做一个顶点,那样就能确立边的关系,以及入度数,之后用拓扑排序求解,先着一个入度为0的顶点,删除其相关的边,循环操作。

代码:

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 30; char str[MAXN * 10]; int in[MAXN], vis[MAXN], g[MAXN][MAXN], sum[MAXN]; int n; void toposort() { int d = 0, low = -10; while (d <= n) { memset(vis, 0, sizeof(vis)); for (int i = 0; i <= n; i++) { if (in[i] == 0) { sum[i] = low; in[i] = -1; vis[i] = 1; d++; } } low++; for (int i = 0; i <= n; i++) { if (vis[i]) { for (int j = 0; j <= n; j++) if (g[i][j]) in[j]--; } } } } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d", &n); scanf("%s", str); memset(in, 0, sizeof(in)); memset(g, 0, sizeof(g)); memset(sum, 0, sizeof(sum)); int cnt = 0; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { if (str[cnt] == '+') { in[j]++; g[i - 1][j] = 1; } else if (str[cnt] == '-') { in[i - 1]++; g[j][i - 1] = 1; } cnt++; } } toposort(); for (int i = 1; i <= n; i++) { if (i == 1) printf("%d", sum[i] - sum[i - 1]); else printf(" %d", sum[i] - sum[i - 1]); } printf(" "); } return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐