UVALive4255-Guess(拓扑排序)
来源：程序员人生 发布时间：2014-10-13 10:57:14 阅读次数：3291次
题目链接
题意：对于一个序列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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
