posts - 2,  comments - 3,  trackbacks - 0
http://acm.timus.ru/problem.aspx?space=1&num=1078

主要思路:i包含j连一有向边i->j,这样问题就变成了给一个有向无环图(DAG),求其最长路,直接spfa就OK啦!

Code
#include<cstdio>

#define MAXN 501

int graph[MAXN][MAXN];
int rd[MAXN];
int dist[MAXN];
int pre[MAXN];
int mark[MAXN];
int seg[MAXN][2];
int maxLen;
int n;

int isContains(int I, int J){
   int reVal = 0;
   if(seg[I][0] < seg[J][0] && seg[I][1] > seg[J][1]){
      reVal = 1;
   }
   if(seg[J][0] < seg[I][0] && seg[J][1] > seg[I][1]){
      reVal = -1;
   }

   return reVal;
}

void spfa(){
   int i = 0;
   int I = 0;
   int t = 0;
   int qHead = 0;
   int qTail = 0;
   int Q[MAXN] = {0};

   for(i = 0; i < n; i++){
      mark[i] = 0;
      pre[i] = -1;
      dist[i] = -MAXN;
   }
   for(i = 0; i < n; i++){
      if(!rd[i]){
         Q[qHead++] = i;
         mark[i] = 1;
         dist[i] = 1;
      }
   }
   do{
      qHead--;
      if(qHead < 0){
         qHead = n - 1;
      }
      I = Q[qHead];
      mark[I] = 0;
      for(i = 0; i < n; i++){
         if(graph[I][i] && dist[I] + 1 > dist[i]){
            pre[i] = I;
            dist[i] = dist[I] + 1;
            if(!mark[i]){
               mark[i] = 1;
               t = qHead - 1;
               if(t < 0)t = n - 1;
               if(qHead != qTail 
                     && dist[i] < dist[Q[t]]){
                     Q[qHead++] = i;
                     if(qHead >= n){
                        qHead = 0;
                     }
               }
               else{
                     qTail--;
                     if(qTail < 0){
                        qTail = n - 1;
                     }
                     Q[qTail] = i;
               }
            }
         }
      }
   }while(qHead != qTail);

   maxLen = -1;
   for(i = 0, I = -1; i < n; i++){
      if(dist[i] > maxLen){
         maxLen = dist[i];
         I = i;
      }
   }
   printf("%d\n", maxLen);
   t = I;
   i = 0;
   while(t != -1){
      if(i){
         printf(" ");
      }
      i = 1;
      printf("%d", t + 1);
      t = pre[t];
   }
   printf("\n");
}

int main(int argc, char* argv[], char* env[])
{
   int i = 0;
   int j = 0;
   int t = 0;
   while(scanf("%d", &n) != EOF){
      for(i = 0; i < n; i++){
         scanf("%d%d", &seg[i][0], &seg[i][1]);
      }
      for(i = 0; i < n; i++){
         rd[i] = 0;
         graph[i][i] = 0;
         for(j = i + 1; j < n; j++){
            t = isContains(i, j);
            graph[i][j] = t > 0 ? 1 : 0;
            graph[j][i] = t < 0 ? 1 : 0;
         }
      }
      for(j = 0; j < n; j++){
         for(i = 0; i < n; i++){
            rd[j] += graph[i][j];
         }
      }
      spfa();
   }
   return 0;
}

posted on 2011-07-20 10:59 Lshain 阅读(278) 评论(0)  编辑 收藏 引用 所属分类: Algorithm题解-timus

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年5月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿

文章分类(46)

文章档案(33)

ACM

Algorithm Link

BLOG

Format analysis

Forum

Math

mirror

OpenGL

Protocol Analyzer

Recent Contests

Search

WIN32 Programming

最新随笔

搜索

  •  

最新评论

阅读排行榜

评论排行榜