UVa 1423 - Guess 拓扑

连接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=543&problem=4169&mosmsg=Submission+received+with+ID+11660014

 

Given a sequence of integers, a₁, a₂,..., a_n <tex2html_verbatim_mark>, we define its sign matrix S such that, S_ij = `` + " <tex2html_verbatim_mark>if a<sub>i</sub> +...+ a<sub>j</sub> > 0 <tex2html_verbatim_mark>; S<sub>ij</sub> = `` - " <tex2html_verbatim_mark>if a_i +...+ a_j < 0 <tex2html_verbatim_mark>; and S_ij = ``0" <tex2html_verbatim_mark>otherwise.

For example, if (a₁, a₂, a₃, a₄) = (- 1, 5, - 4, 2) <tex2html_verbatim_mark>, then its sign matrix S <tex2html_verbatim_mark>is a 4×4 <tex2html_verbatim_mark>matrix:

 

 

 

We say that the sequence (-1, 5, -4, 2) generates the sign matrix. A sign matrix is valid if it can be generated by a sequence of integers.

Given a sequence of integers, it is easy to compute its sign matrix. This problem is about the opposite direction: Given a valid sign matrix, find a sequence of integers that generates the sign matrix. Note that two or more different sequences of integers can generate the same sign matrix. For example, the sequence (-2, 5, -3, 1) generates the same sign matrix as the sequence (-1,5, -4,2).

Write a program that, given a valid sign matrix, can find a sequence of integers that generates the sign matrix. You may assume that every integer in a sequence is between -10 and 10, both inclusive.

 

Input 

Your program is to read from standard input. The input consists of T <tex2html_verbatim_mark>test cases. The number of test cases T<tex2html_verbatim_mark>is given in the first line of the input. Each test case consists of two lines. The first line contains an integer n <tex2html_verbatim_mark>(1n10) <tex2html_verbatim_mark>, where n <tex2html_verbatim_mark>is the length of a sequence of integers. The second line contains a string of n(n + 1)/2 <tex2html_verbatim_mark>characters such that the first n <tex2html_verbatim_mark>characters correspond to the first row of the sign matrix, the next n - 1 <tex2html_verbatim_mark>characters to the second row, ... <tex2html_verbatim_mark>, and the last character to the n <tex2html_verbatim_mark>-th row.

 

Output 

Your program is to write to standard output. For each test case, output exactly one line containing a sequence of n <tex2html_verbatim_mark>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

 

 

 

 

 

 

 

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10 + 5;

int n, G[maxn][maxn]; // 注意本题结点编号为0~n
int c[maxn];
vector<int> topo;

bool dfs(int u){
  c[u] = -1;
  for(int v = 0; v <= n; v++) if(G[u][v]) {
    if(c[v]<0) return false;
    else if(!c[v]) dfs(v);
  }
  c[u] = 1; topo.push_back(u);
  return true;
}

bool toposort(){
  topo.clear();
  memset(c, 0, sizeof(c));
  for(int u = 0; u <= n; u++) if(!c[u])
    if(!dfs(u)) return false;
  reverse(topo.begin(), topo.end());
  return true;
}

// 用并查集合并相等结点
int pa[maxn];
int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; }

int main() {
  int T;
  scanf("%d", &T);
  while(T--) {
    char input[100], S[11][11];
    scanf("%d%s", &n, input);
    int idx = 0;
    for(int i = 0; i <= n; i++) pa[i] = i;
    for(int i = 1; i <= n; i++)
      for(int j = i; j <= n; j++) {
        S[i][j] = input[idx++];
        if(S[i][j] == '0') pa[j] = i-1; // sum[j]-sum[i-1]=0，因此j和i-1是等价结点
      }

    // 若前缀和sum[a] < sum[b]，连边a->b，在拓扑序中a会在b的前面
    memset(G, 0, sizeof(G));
    for(int i = 1; i <= n; i++)
      for(int j = i; j <= n; j++) {
        if(S[i][j] == '-') G[findset(j)][findset(i-1)] = 1; // sum[j]-sum[i-1] < 0
        if(S[i][j] == '+') G[findset(i-1)][findset(j)] = 1; // sum[j]-sum[i-1] > 0
      }
    toposort();
    int sum[maxn], cur = 0;
    for(int i = 0; i <= n; i++) sum[topo[i]] = cur++; // 按照拓扑序依次赋值0, 1, 2, ...
    for(int i = 1; i <= n; i++) {
      sum[i] = sum[findset(i)];
      if(i > 1) printf(" ");
      printf("%d", sum[i] - sum[i-1]); // 注意，sum[0]未必等于0
    }
    printf("\n");
  }
  return 0;
}