UVALive4255-Guess(拓撲排序)
來源：程序員人生 發布時間：2014-10-13 10:57:14 閱讀次數：3485次
題目鏈接
題意：對于一個序列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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
