poj-3687Labeling Balls(反向建图+优先队列+逆向输出)

傷城~ 2022-08-10 09:16 113阅读 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;12675</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3647</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

这个题和逃生那个题是一类的，都是要尽量把小的往前排，所以要反向建图，如果用到邻接表的话，就还要用到优先队列

我用了两种方法

1，用到邻接表（反向拓扑+优先队列+逆向输出）

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;
    int head[500],degree[500],result[450],m,n,t;
    struct node {
    	int to,next;
    }s[400000];
    void add(int x,int y)
    {
    	s[t].to=y;
    	s[t].next=head[x];
    	head[x]=t++;
    }
    int topo()
    {
    	int i,j,p;
    	priority_queue<int >Q;
    	for(i=1;i<=m;i++)
    	if(degree[i]==0)
    	Q.push(i);
    	p=m;
    	while(!Q.empty())
    	{
    		int w=Q.top();
    		Q.pop();
    		result[w]=p--;
    		
    		for(int k=head[w];k!=-1;k=s[k].next)
    		{
    			int e=s[k].to;
    			degree[e]--;
    			
    			if(!degree[e])
    			Q.push(e);
    		}
    	}
    	if(p==0)
    	return 1;
    	
    	return 0;
    }
    int main()
    {
    	int N,a,b,i,j;
    	scanf("%d",&N);
    	while(N--)
    	{
    		t=0;
    		memset(degree,0,sizeof(degree));
    		memset(head,-1,sizeof(head));
    		scanf("%d%d",&m,&n);
    		for(i=0;i<n;i++)
    		{
    			scanf("%d%d",&a,&b);
    			add(b,a);
    			degree[a]++;
    		}
    		int qw=topo();
    		if(qw)
    		{
    			for(i=1;i<m;i++)
    			printf("%d ",result[i]);
    			printf("%d\n",result[i]);
    		}
    		else
    		printf("-1\n");
    	}
    	return 0;
    }

2，反向建图，正向输出

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    using namespace std;
    int map[500][500],degree[500],m,n;
    void topo()
    {
    	int i,j,a,result[500],t=0,mark;
    	for(i=m;i>0;i--)
    	{
    	    mark=-1;
    		for(j=m;j>=1;j--)
    		{
    			if(degree[j]==0)
    			{
    				mark=j;
    				break;
    			}
    		}
    		if(mark==-1)
    		break;
    		degree[mark]=-1;
    		result[j]=i;
    		for(int k=1;k<=m;k++)
    		{
    			if(map[mark][k])
    			degree[k]--;
    		}
    	}
    	if(mark==-1)
    	printf("-1\n");
    	else
    	{
    		for(i=1;i<m;i++)
    		printf("%d ",result[i]);
    		printf("%d\n",result[i]);
    	}
    }
    int main()
    {
    	int N,i,j,a,b;
    	scanf("%d",&N);
    	while(N--)
    	{
    		memset(map,0,sizeof(map));
    		memset(degree,0,sizeof(degree));
    		scanf("%d%d",&m,&n);
    		for(i=0;i<n;i++)
    		{
    			scanf("%d%d",&a,&b);
    			if(!map[b][a])
    			{
    				map[b][a]=1;
    				degree[a]++;
    			}
    		}
    		topo();
    	}
    	return 0;
    }