poj 3687(拓扑排序)

http://poj.org/problem?id=3687

题意：有一些球他们都有各自的重量，而且每个球的重量都不相同，现在，要给这些球贴标签。如果这些球没有限定条件说是哪个比哪个轻的话，那么默认的前面比后的要请，而且这n个球的重量也正好是分布在1-n这个范围内，现在要你求出他们各自所占的重量。

思路：最开始，我也是想到了用拓扑排序，但是它的入度值我确定不了，然后去看discuss，里面说对每个判断条件反向建图，然后在用最大优先队列。我不理解这是什么意思。然后看了下别人的博客，模拟了一下大概的过程。

比如说

4 1

那么答案是2 3 4 1

反向建图，那么也就是digree[ 4 ] ++；

然后，其他的数入度值都是为0，所以都进优先队列。

那么现在优先队列就是有 1 2 3 这三个数。

然后，location[ 3 ] = 4;

再去寻找有没有与3相比较过的数。

然后, location[ 2 ] = 3;

再去找有没有与2相比较过的数。

然后,location[ 1 ] = 2;

再去找有没有与1比较过的数，如果有的话，把那么数入队列，那么4就入了队列。

然后,location[ 4 ] = 1;

然后反向输出，这就是结果，而那么 4 3 2 1 这是怎么来的呢，首先用一个变量num等于n。

然后每使用一次，这个变量就--。上面的也就是相当于 location[ 3 ] = 4 --。

 #include <stdio.h>

 #include <string.h>

 #include <queue>

 #define maxn 210

 using namespace std;

 int digree [ maxn ];        //这个就是入度值。

 int judge [ maxn ][ maxn ];     //这个是用来判断有没有重边的。

 int location [ maxn ];

 int m,n;

 priority_queue<int >s;     //这个是默认的最大优先队列。

 int topsort()

 {

     int num = n;

     for( int i =  ; i <= n ; i++ )

         if(!digree[ i ]) s.push( i );

     if( s.empty() )  return ;    //如果没有入度为0的，则说明构成了一个环。

     while( !s.empty() )

     {

         int tmp =s.top();

         s.pop();

         location [ tmp ] = num--;

         for( int i =  ; i <= n ; i++ )

         {

             if( judge[ i ][ tmp ] )

             {

                 judge[ i ][ tmp ] = ;

                 digree[ i ] --;

                 if( !digree[ i ] ) s.push( i );

             }

         }

     }

     if( num !=  ) return ;    //如果这里Num 不能等于0，那么说明最少还有两个是无法确定的。

     return ;

 }

 int main()

 {

     int t,a,b;

     scanf("%d",&t);

     while( t -- )

     {

         memset( digree ,  , sizeof( digree ) );

         memset( judge ,  , sizeof( judge ) );

         memset( location ,  , sizeof( location ) );

         scanf("%d%d",&n,&m);

         for( int i =  ; i <= m ; i ++ )

         {

             scanf("%d%d",&a,&b);

             if(judge[ a ][ b ] > ) continue;   //判重。

             judge[ a ][ b ] = ;

             digree [ a ] ++;

         }

         a = topsort();

         if( a ) {

             int i = ;

             for( ; i < n ; printf("%d ",location[ i++ ]) );

             printf("%d\n",location[ i ]);

         }

         else printf("-1\n");

     }

     return ;

 }

巴特西

poj 3687(拓扑排序)

最新文章

热门文章