poj 3687 Labeling Balls(拓扑排序)

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

非常坑的一道题，最后快要绕晕了。。

题意：有N个球，重量分别是1~N，给着n个球贴上标签。输入n，m代表n个球和m条边(a b)，代表 标签为a的要比标签为b的轻。最后输出标签1~N对应的重量（注意是重量，而不是轻重关系），还有要注意“ 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... ”,意思是标签小的要尽可能贴在重量小的球上。

思路：因为标签小的要尽可能贴在重量小的球上，所以拓扑排序时要使标签小的尽可能的靠前。所以只是传统的拓扑排序每次取优先队列中入度为0并且数最小的不对的。因为即使该点最小，它后面连着的点未必是最小的。

例如上图，若先取入度为0且最小的话，是先取出3，而我们的目的是让标号小的尽量靠前，即应该让1尽量靠前，这与先取出3相违背，这时应该先取出6才能使1尽量靠前。对于2,8，2肯定先出队列。归纳起来便是对于若干平行的路径，小的头部不一定排在前面（如3），但大的尾部一定排在后面（如8）.

1. 把所有出度为 0 的节点放进优先队列 PQ
2. WHILE： PQ 不是空队列
3.     从 PQ 中取出编号最大的元素 a，把 a 添加到答案的头部。
4.     FOR：所有指向 a 的边 b → a
5.        把 b 的出度减 1。如果 b 的出度变为 0，则把 b 放进优先队列 PQ。  

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

int n,m;
int out[210];
int topo[210];
int map[210][210];
priority_queue < int, vector<int>,less<int> > que;

int toposort()
{
	while(!que.empty()) que.pop();
	int cnt = 1;
	memset(topo,0,sizeof(topo));
	for(int i = 1; i <= n; i++)
		if(out[i] == 0)
			que.push(i);

	while(!que.empty())
	{
		int u = que.top();	//每次取出队列中最大的
		que.pop();
		topo[cnt++] = u;  
		for(int i = 1; i <= n; i++)
		{
			if(map[i][u] == 1)
			{
				out[i]--;
				if(out[i] == 0)
					que.push(i);
			}
		}
	}
	if(cnt == n+1)
		return 1;
	return 0;

}

int main()
{
	int test;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d %d",&n,&m);
		memset(out,0,sizeof(out));
		memset(map,0,sizeof(map));
		int flag = 1;

		for(int i = 0; i < m; i++)
		{
			int a,b;
			scanf("%d %d",&a,&b);
			if(!map[a][b])
			{
				map[a][b] = 1;
				out[a]++;
			}
			if(a == b)
				flag = 0;
		}
		if(!flag)
		{
			printf("-1\n");
			continue;
		}
		int tmp[210];
		int ans = toposort();
		if(ans == 0)
			printf("-1\n");
		else
		{
			for(int i = 1; i <= n; i++)
				tmp[ topo[i] ] = n+1-i;	//编号，tmp[]存的是拓扑排序的逆序.
			for(int i = 1; i <= n-1; i++)
				printf("%d ",tmp[i]); //输出编号1~n对应的重量
			printf("%d\n",tmp[n]);
		}

	}
	return 0;
}

poj 3687 Labeling Balls(拓扑排序),布布扣,bubuko.com

poj 3687 Labeling Balls(拓扑排序)

原文：http://blog.csdn.net/u013081425/article/details/22201843