POJ3687 Labeling Balls（拓撲排序的應用）

給出一些球，從1~N編号，他們的重量都不相同，也用1~N标記加以區分（這裡真心惡毒啊，估計很多WA都是因為這裡），然後給出一些限制條件，< a , b >要求編号為 a 的球必須比 b 輕，現在要求按編号升序輸出每個球的重量，如果有多種解，輸出字典序最小的那個。

例如：

input：

1

5 4

5 1

4 2

1 3

2 3

output：

2 4 5 3 1

輸出的意思是，編号為 1 的球的重量是 2，編号為 2 的球重量為 5，編号 3 的球重量為 5，編号 4 的球重量為 3，編号 5 的球重量為 1 。

顯然的這滿足了 input 的所有限制條件，而且字典序最小。

開始直接拓撲整的，WA掉了，看discuss裡面各大牛X提示，才發現我這樣的不到要求的序列……

需要注意的：

node1：反向建圖

node2：考慮重邊

ps：感謝

http://imlazy.ycool.com/post.2144071.html

http://www.answeror.com/archives/23913

兩組給力資料：http://poj.org/showmessage?message_id=145313

我的代碼：

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int N = 210;

struct point{
	int id,de;//入度
	bool operator < (const point &a) const{
		return a.id > id;
	}
};

point p[N];
int n,m,map[N][N],vis[N];

void getmap()
{
	int i,a,b;
	for(i=1;i<=n;p[i].id=i,p[i++].de=0);
	memset(map,0,sizeof(map));
	while(m--){
		scanf("%d%d",&a,&b);
		if(map[b][a]==0){
			map[b][a]=1;p[a].de++;
		}
	}
}

void solve()
{
	point cur;
	priority_queue <point> q;
	int i,j,k=1,ans[N],a[N];
	memset(vis,0,sizeof(vis));
	
	for(i=1;i<=n;i++){//所有入度為0的點先入隊
		if(p[i].de==0)q.push(p[i]);
	}
	
	int tol=0;
	while(!q.empty()){
		cur=q.top();
		q.pop();
		if(cur.de==0 && !vis[cur.id]){
			a[k++]=cur.id;
			vis[cur.id]=1;
			tol++;
			for(j=1;j<=n;j++){
				if(!vis[ p[j].id ]){
					if(map[cur.id][p[j].id])p[j].de--;
					if(p[j].de==0)q.push(p[j]);
				}
			}
		}
	}
	if(tol<n)printf("-1");
	else {
		for(i=1;i<k;i++)
			ans[ a[k-i] ] = i;
		printf("%d",ans[1]);
		for(i=2;i<=n;i++)
			printf(" %d",ans[i]);
	}
	puts("");
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		getmap();
		solve();
	}
	return 0;
}