程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> uva La 4255 Guess （拓撲排列）

uva La 4255 Guess （拓撲排列）

編輯：關於C語言

拓撲排列適用於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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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];
vectora;
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;
}