uva La 4255 Guess （拓扑排列）

uva La 4255 Guess （拓扑排列）

拓扑排列适用于DAG有向无环图。

构造所有节点之间的单向边。

具体问题中，抽象出点和边（单向边），单向边对应于具体的点之间的大小关系或需求关。

构造出图后，问题中的所有的关系都可以用点之间的有向边表示。

此题中。

（1）将每个数字构造成点时，不易表示。

将前缀和构造成点，而所有的区间和都可以有两个前缀的差得到。则由所有区间和正负或为0，可以得到不同前缀之间的大小关系，即个点之间的单向边。

（2）注意到可能为零，表示2个前缀值相等，即图中可能有两点成环。

处理方法：

dis[i][j]  = 0，表示相等，1表示i-->j,-1表示j--i.

每次得到一个点时，将所有的dis[][] = 0,的点取出赋相同的值。

//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//LOOP
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FD(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
//OUTPUT
#define WI(n) printf("%d\n", n)
#define WS(s) printf("%s\n", s)

typedef long long LL;
const int INF = 1000000007;
const double eps = 1e-10;
const int maxn = 20;

int T, n;
int suf[maxn];
int dis[maxn][maxn];
int du[maxn];
vector<int>a;
void solve()
{
    int tot = 0;
    int val = 0;
    while (tot < n + 1)
    {
        for (int i = 0; i <= n; i++)
        {
            if (du[i] == 0)
            {
                a.clear();
                a.push_back(i);
                suf[i] = val;
                for (int j = 0; j <= n; j++)
                {
                    if (i != j && du[j] != -1 && dis[i][j] == 0)
                    {
                        suf[j] = val;
                        a.push_back(j);
                    }
                }
                val++;
                tot += a.size();
                for (int j = 0; j < a.size(); j++)
                {
                    int x = a[j];
                    for (int r = 0; r <= n; r++)
                        if (du[r] != -1 && dis[x][r] == 1)
                            du[r]--;
                }
                for (int j = 0; j < a.size(); j++)
                    du[a[j]] = -1;
            }
        }
    }
    int x = suf[0];
    for (int i = 0; i <= n; i++)
        suf[i] -= x;
    for (int i = 1; i <= n; i++)
    {
        if (i != 1) printf(" ");
        printf("%d", suf[i] - suf[i -1]);
    }
    puts("");
}
int main ()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d", &n);
        memset(dis, 0, sizeof(dis));
        memset(du, 0, sizeof(du));
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                char x;
                scanf(" %c", &x);
                if (x == ‘-‘)
                {
                    du[i - 1]++;
                    dis[j][i - 1] = 1;
                    dis[i - 1][j] = -1;
                }
                else if (x == ‘+‘)
                {
                    du[j]++;
                    dis[i - 1][j] = 1;
                    dis[j][i - 1] = -1;
                }
            }
        }
        solve();
    }

    return 0;
}

uva La 4255 Guess （拓扑排列）,布布扣,bubuko.com

uva La 4255 Guess （拓扑排列）

原文：http://blog.csdn.net/guognib/article/details/21707145