POJ 3684-Labeling Balls（反向拓扑排序-按条件排序输出重量）

红太狼 2022-06-18 07:17 136阅读 0赞

Labeling Balls

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;14408</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;4213</td> 
  </tr> 
 </tbody> 
</table>

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

Source

[POJ Founder Monthly Contest – 2008.08.31][POJ Founder Monthly Contest _ 2008.08.31], windy7926778

## 题目意思： ##

N个瓶子重量为1~N，给它们贴上1~N的标签（随机，未按重量贴标签），给出M个条件A B指出标签为A的瓶子重量小于标签为B的瓶子，计算按顺序并给出1~N号瓶子的重量。

## 解题思路： ##

优先队列+反向拓扑+逆序输出，建议先搞一搞[HDU 4857][]。

这题的坑点就是要输出的不是重量由小到大瓶子的标签号，而是按顺序并给出1~N号瓶子的重量，所以在计算出重量顺序后再用一个数组记录1~N的重量后输出。

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<set>
    #include<cstdlib>
    #include<iostream>
    #include<queue>
    #include<algorithm>
    using namespace std;
    #define MAXN 100010
    #define INF 0x3f3f3f3f
    int n,m;
    int indegree[MAXN];
    vector<int> v[MAXN];
    struct cmp
    {
        bool operator()(const int &a,const int &b)
        {
            return a<b;//从大到小
        }
    };
    
    void Topsort()//拓扑排序
    {
        priority_queue<int,vector<int>,cmp> q;
        int p[MAXN];
        int ip=0;
        memset(p,0,sizeof(p));
        for(int i=0; i<n; i++)
            if(indegree[i]==0)
                q.push(i);
        while(!q.empty())
        {
            int temp=q.top();
            p[++ip]=temp;
            q.pop();
            for(int i=0; i<v[temp].size(); i++)
            {
                indegree[v[temp][i]]--;
                if(indegree[v[temp][i]]==0)
                    q.push(v[temp][i]);
            }
        }
        int ans[MAXN];
        if(ip<n) printf("-1\n");
        else
        {
            int cnt=1;
            for(int i=ip; i>=1; --i)//重量大小应当逆向输出
                ans[p[i]+1]=cnt++;//记录1~N的重量
            for(int i=1; i<cnt-1; ++i)
                printf("%d ",ans[i]);
            printf("%d\n",ans[cnt-1]);
        }
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
    //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        int t;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i=0; i<=n; i++) v[i].clear();//注意初始化清空
            memset(indegree,0,sizeof(indegree));
            for(int i=0; i<m; ++i)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                --a,--b;
                v[b].push_back(a);//逆向建图
                ++indegree[a];
            }
            Topsort();
        }
        return 0;
    }

[POJ Founder Monthly Contest _ 2008.08.31]: http://poj.org/searchproblem?field=source&key=POJ+Founder+Monthly+Contest+%E2%80%93+2008.08.31
[HDU 4857]: http://blog.csdn.net/mikasa3/article/details/63263711