POJ 3678（拓扑排序+优先队列）

POJ 3678

 

（1）题意：

给出n个点，每个点都有一个重量值有两个限制条件，

一是n个点每个点的重量都不一样

二是m个限制中有a求的重量小于b球的重量。

而且尽可能让求的质量小一点，每个从1~n每次尽量让这个求的质量小一些。

如果结果存在，输出n个点的质量，否则输出-1.

 

（2）思路：

一开始以为是差分约束，后来发现限制条件解出来的解不能保证所有的点的值都不同。

后来参考网上的文章发现可以用拓扑排序来做。

将限制作为边，y的值一定大于x的值，所以在先给较大的y赋值，然后在处理x

建立一条从y到x的边。

然后拓扑排序，因为要求从1~n的质量的质量尽可能较小，可以先确立最大的质量为n，然后处理其他点，

就是拓扑排序+优先队列就好了。

 

（3）代码：

参考文章

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 220;
priority_queue <int> q;
int du[maxn],vis[maxn],mp[maxn][maxn],m,n,dis[maxn],fg;
void Topo(){
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++)
	if(du[i]==0){
		q.push(i);
	}
	int val = n;
	while(!q.empty()){
		int x = q.top();q.pop();
		for(int i=n;i>=1;i--)
		if(du[i]>0&&mp[x][i]!=0){
			du[i]--;
			if(du[i]==0){
				q.push(i);
			}
		}
		dis[x] = val--;
	}
	if(val!=0) fg = 1;
}
int main(void){
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<=n;i++){
			for(int j=0;j<=n;j++) mp[i][j] = 0;
			vis[i] = 0;dis[i] = 0;du[i] = 0;
		}
		fg = 0;
		for(int i=0;i<m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			if(x==y){
				fg = 1;
			}
			if(mp[y][x]==0){
				mp[y][x] = 1;
				du[x]++;
			}
		}
		if(fg==1) printf("-1\n");
		else{
			Topo();
			if(fg==1){
				printf("-1\n");
				continue;
			}
			for(int i=1;i<=n;i++){
				if(i>1) printf(" ");
				printf("%d",dis[i]);
			}
			printf("\n");
		}
	}
	return 0;
}