设为首页 加入收藏

TOP

uva La 4255 Guess （拓扑排列）
2014-11-23 20:00:06 来源: 作者: 【大 中 小】 浏览:31次
Tags：uva 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 
  
   
#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]; vector
               
                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; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：Objective-C基础笔记（5）Protocol 下一篇：c编程：整数的个数。

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: