uva 1423 (拓扑排序)

题意是给你一个长度小于10的数列，再给你任意子段和的符号。让你输出这一个数列，本题难度在于如何构图。

首先要说明的是由于给你的矩阵是任意子段和的符号，所以我们求解的时候可以先求解前缀和，然后也能很方便的在输出时将其转换成我们要得数列。

再说一下如何构图，首先我们定义边的含义：i->j的边表示s[i]>s[j]。一旦想到这个算法就清晰了，我们只要进行拓扑排序，然后再排序构成中对于每一个s[i]进行赋值就OK了。

代码如下：

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#define INF 0x7fffffff
#define ll long long
#define eps 1e-6
#define LEN 13

using namespace std;

int Map[LEN][LEN], Indegree[LEN], s[LEN], n, vis[LEN];

void topsort(){
    queue<int> q;
    memset(vis, 0, sizeof vis);
    for(int i=0; i<=n; i++){
        if(Indegree[i]==0){
            q.push(i);
            s[i] = 10;
            vis[i] = 1;
        }
    }
    while(!q.empty()){
        int vex = q.front(); q.pop();
        for(int i=0; i<=n; i++){
            if(Map[vex][i]){
                Indegree[i]--;
                if(Indegree[i]==0 && vis[i]==0){
                    vis[i] = 1;
                    q.push(i);
                    s[i] = s[vex]-1;
                }
            }
        }
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);

    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        memset(Map, 0, sizeof Map);
        memset(Indegree, 0, sizeof Indegree);
        memset(s, 0, sizeof s);
        for(int i=1; i<=n; i++){
            for(int j=i; j<=n; j++){
                char temp;
                cin >> temp;
                if(temp=='+'){
                    Map[j][i-1] = 1;
                    Indegree[i-1]++;
                }else if(temp=='-'){
                    Map[i-1][j] = 1;
                    Indegree[j]++;
                }
            }
        }
        topsort();
        for(int i=1; i<=n; i++){
            printf("%d", s[i]-s[i-1]);
            if(i!=n) printf(" ");
            else printf("
");
        }
    }
    return 0;
}