http://poj.org/problem?id=3687
这是道拓扑稍稍变形的题。。。搞了一天,差不多理解了,感觉真是道不错的题,所以来写下题解。
关键是理解题意。“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…”是说,编号时尽可能让重量小的往前排,这点直接决定了拓扑应该怎么变化。
http://imlazy.ycool.com/post.2144071.html这篇帖子讲的很精到。
总之就是排序时以出度(一般的拓扑是入度)作为标准排时,就可以保证越大的越靠后。
详细放到程序里说:

#include"stdio.h"
#include"string.h"
int in[205],out[205],map[205][205],n,m;//in存放出度,out临时存放编号排序(不是最终的重量排序,而且是按逆向排好的),map存相对关系
int toposort()
{
	int i,j,w=1,max,vis[205];
	memset(vis,0,sizeof(vis));//vis记录是否访问过
	for(i=1;i<=n;i++)//每次循环找出当下出度为0的最大点
	{
		max=-1;
		for(j=1;j<=n;j++)
		{
			if(in[j]==0&&j>max&&!vis[j])
				max=j;
		}
		if(max==-1)
			return 0;//这里太关键了,不加就会wa,也就是判断有没有环(max仍是-1,说明此时没有出度为0的点)
		vis[max]=1;
		out[w++]=max;
		for(j=1;j<=n;j++)
		{
			if(map[j][max]==1)
				in[j]--;//找到当下的出度为零的点后就要把以它做为终点的结点的出度-1
		}
	}
	return 1;
}
int main()
{
	int p1,p2,i,j,T,flag;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		flag=0;
		memset(map,0,sizeof(map));
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		while(m--)
		{
			scanf("%d%d",&p1,&p2);
			if(p1==p2)
				flag=1;//自环排除
			if(flag==0)
			{
				if(map[p1][p2]==0)
				{
					in[p1]++;//p1出度+1
					map[p1][p2]=1;//p1比p2靠前
					map[p2][p1]=-1;//p2比p1靠后
				}
				else if(map[p1][p2]==1)
					continue;
				else if(map[p1][p2]==-1)//已经有了p1在p2后面,所以直接标记无解
					flag=1;
			}
		}
		if(flag==1)
			printf("-1");
		else
		{
			if(toposort()==0)
				printf("-1");
			else
			{
				for(i=1;i<=n;i++)
				{
					for(j=1;j<=n;j++)
					{
						if(out[j]==i)
							break;
					}
					printf("%d",n-j+1);//将编号排序转为重量(out里存的是逆序)
					if(i!=n)
						printf(" ");
				}
			}
		}
		printf("\n");
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation