Poj 3687 Labeling Balls (拓扑排序)

今天药忘吃喽~ 2022-08-25 09:13 27阅读 0赞

题意：n个重量为1~n的球，给定一些编号间的重量比较关系，现在给每个球编号，在符合条件的前提下使得编号小的球重量小。（先保证1号球最轻，其次2号……）

思路：拓扑排序，反向建图。利用优先队列保证每次被处理点的编号最小。

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N=205;
    
    struct Node
    {
    	int id,degree; //初始编号 入度
    	bool operator < (const Node &a) const
    	{
    		return id<a.id;
    	}
    }data[N];
    
    int n,m,cnt;
    bool graph[N][N],vis[N];
    int ans[N],s[N];
    
    bool Deal ()
    {
    	priority_queue <Node> q;
    	int i;
    	for (i=1;i<=n;i++) //所有入度为0的点先入队
    		if (data[i].degree==0)
    			q.push(data[i]);
    
    	while (!q.empty())
    	{
    		Node cur=q.top();
    		q.pop();
    		if (cur.degree==0 && vis[cur.id]==false)
    		{
    			s[cnt++]=cur.id;  //记录处理顺序
    			vis[cur.id]=true;
    			for (i=1;i<=n;i++)
    				if (vis[ data[i].id ]==false)
    				{
    					if (graph[cur.id][data[i].id])
    						data[i].degree--;
    					if (data[i].degree==0)
    						q.push(data[i]);
    				}
    		}
    	}
    	if (cnt<=n) return true; //有环
    	return false;
    }
    
    int main ()
    {
    	int T,i;
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%d%d",&n,&m);
    		for (i=1;i<=n;i++)
    			data[i].id=i,data[i].degree=0;
    		cnt=1;
    		
    		memset(graph,false,sizeof(graph));
    		memset(vis,false,sizeof(vis));
    		memset(ans,0,sizeof(ans));
    		memset(s,0,sizeof(s));
    		while (m--)
    		{
    			int a,b;
    			scanf("%d%d",&a,&b);
    			if (graph[b][a]==false)
    			{//处理重边,避免影响入度
    				graph[b][a]=true;
    				data[a].degree++;
    			}
    		}
    		if (Deal())
    			printf("-1\n");
    		else
    		{
    			for (i=1;i<cnt;i++)
    				ans[ s[cnt-i] ] = i;
    			for (i=1;i<=n;i++)
    				printf(i==n?"%d\n":"%d ",ans[i]);
    		}
    	}
    	return 0;
    }
    
    /*
    测试数据转自 http://poj.org/showmessage?message_id=145313
    2
    
    5 4
    5 1
    4 2
    1 3
    2 3
    
    10 5
    4 1
    8 1
    7 8
    4 1
    2 8
    ans:
    2 4 5 3 1        逆向建图
    5 1 6 2 7 8 3 4 9 10  没有判重边的话就输出 -1
    */