poj 3687 Labeling Balls

Myth丶恋晨 2021-11-10 13:14 150阅读 0赞

Description

Windy has *N* balls of distinct weights from 1 unit to *N* units. Now he tries to label them with 1 to *N* in such a way that:

1.  No two balls share the same label.
2.  The labeling satisfies several constrains like "The ball labeled with *a* is lighter than the one labeled with *b".*

Can you help windy to find a solution?

Input

The first line of input is the number of test case. The first line of each test case contains two integers, *N* (1 ≤ *N* ≤ 200) and *M* (0 ≤ *M* ≤ 40,000). The next *M* line each contain two integers *a* and *b* indicating the ball labeled with *a* must be lighter than the one labeled with *b*. (1 ≤ *a, b* ≤ *N*) There is a blank line before each test case.

Output

For each test case output on a single line the balls' weights from label 1 to label *N*. If several solutions exist, you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on... If no solution exists, output -1 instead.

Sample Input

5
    
    4 0
    
    4 1
    1 1
    
    4 2
    1 2
    2 1
    
    4 1
    2 1
    
    4 1
    3 2

Sample Output

1 2 3 4
    -1
    -1
    2 1 3 4
    1 3 2 4
    
    题意：：N个标签分别是1,2,3......N。N个小球，质量分别是1,2,3.....N。现在给球贴标签，有M个限制条件。其中每个限制条件为贴标签a的球要比贴标签b的球轻。
    依次输出标签1的球的质量，标签2的球的质量.........且字典序最小。
    
    题解：如果没有字典序最小的限制条件，那么标签a比标签b轻，则建一条边从a到b。如果图存在环在，则无解。如果图没环，直接进行拓扑排序（正向），将每次选出的点贴给当前最小的质量的
    球，
    即可求得一组解。
    题目要求让字典序最小，刚开始想的是正向建图，然后每次选取一个最小的质量用队列进行拓扑排序，可是这样是错误的，这样只能保证在每一步（当前情况，题目要求得是结果）的选择中使当前入度为0并且编号最小的球重量最小，
    并不能保证得到的结果中编号最小的球重量最轻。后来采用了反向建图，在拓扑排序中每一步选择当前最大的编号给他分配当前最大的重量（即此时入度为零的球），这样可以保证得到的结果f

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <iostream>
     2 #include <cstdio>
     3 #include <cstring>
     4 #include <algorithm>
     5 #include <cstdlib>
     6 #include <cmath>
     7 #include <queue>
     8 #include <stack>
     9 #include <limits>
    10 #define MAX 205
    11 
    12 using namespace std;
    13 int G[MAX][MAX];
    14 int in[MAX];
    15 int data[MAX];
    16 int main()
    17 {
    18     int t;
    19     scanf("%d",&t);
    20     while(t--)
    21     {
    22         // getchar();
    23         int a,b,m,n;
    24         scanf("%d%d",&n,&m);
    25         memset(G,0,sizeof(G));
    26         memset(in,0,sizeof(in));
    27         while(m--)
    28         {
    29             scanf("%d%d",&a,&b);
    30             if(!G[b][a])//重复边
    31             {
    32                 G[b][a]=1;
    33                 in[a]++;
    34             }
    35         }
    36         int k=0;
    37         for(int i=n; i>=1; i--)
    38         {
    39             int flag=1,s;
    40             for(int j=n; j>=1; j--)
    41                 if(in[j]==0)
    42                 {
    43                     data[j]=i;//i为最外层的循环，将当前度为零的即最大的质量放在最大编号球
    44                     in[j]--;
    45                     flag=0;
    46                     k++;
    47                     s=j;
    48                     break;
    49                 }
    50             if(flag)
    51             {
    52                 k=0;
    53                 break;
    54             }
    55             for(int j=n; j>=1; j--)
    56                 if(G[s][j])
    57                     in[j]--;
    58         }
    59         if(k!=n)
    60         {
    61             printf("-1");   printf("\n");
    62         }
    63         else
    64             for(int i=1;i<=n;i++)
    65                 printf("%d%c",data[i],i==n?'\n':' ');
    66 
    67     }
    68     return 0;
    69 }

转载于:https://www.cnblogs.com/hbhdhd/p/11172767.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/b3ffba2c59424298a09aff2b090e5322.png