首页 技术 正文
技术 2022年11月24日
0 收藏 878 点赞 4,734 浏览 1446 个字

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

题意:有一些球他们都有各自的重量,而且每个球的重量都不相同,现在,要给这些球贴标签。如果这些球没有限定条件说是哪个比哪个轻的话,那么默认的前面比后的要请,而且这n个球的重量也正好是分布在1-n这个范围内,现在要你求出他们各自所占的重量。

思路:最开始,我也是想到了用拓扑排序,但是它的入度值我确定不了,然后去看discuss,里面说对每个判断条件反向建图,然后在用最大优先队列。我不理解这是什么意思。然后看了下别人的博客,模拟了一下大概的过程。

比如说

4 1

4 1

那么答案是2 3 4 1

反向建图,那么也就是digree[ 4 ] ++;

然后,其他的数入度值都是为0,所以都进优先队列。

那么现在优先队列就是有 1 2 3 这三个数。

然后,location[ 3 ] = 4;

再去寻找有没有与3相比较过的数。

然后, location[ 2 ] = 3;

再去找有没有与2相比较过的数。

然后,location[ 1 ] = 2;

再去找有没有与1比较过的数,如果有的话,把那么数入队列,那么4就入了队列。

然后,location[ 4 ] = 1;

然后反向输出,这就是结果,而那么 4 3 2 1 这是怎么来的呢,首先用一个变量num等于n。

然后每使用一次,这个变量就–。上面的也就是相当于 location[ 3 ] = 4 –。

 #include <stdio.h>
#include <string.h>
#include <queue>
#define maxn 210 using namespace std; int digree [ maxn ]; //这个就是入度值。
int judge [ maxn ][ maxn ]; //这个是用来判断有没有重边的。
int location [ maxn ];
int m,n; priority_queue<int >s; //这个是默认的最大优先队列。 int topsort()
{
int num = n;
for( int i = ; i <= n ; i++ )
if(!digree[ i ]) s.push( i );
if( s.empty() ) return ; //如果没有入度为0的,则说明构成了一个环。
while( !s.empty() )
{
int tmp =s.top();
s.pop();
location [ tmp ] = num--;
for( int i = ; i <= n ; i++ )
{
if( judge[ i ][ tmp ] )
{
judge[ i ][ tmp ] = ;
digree[ i ] --;
if( !digree[ i ] ) s.push( i );
}
}
}
if( num != ) return ; //如果这里Num 不能等于0,那么说明最少还有两个是无法确定的。
return ;
} int main()
{
int t,a,b;
scanf("%d",&t);
while( t -- )
{
memset( digree , , sizeof( digree ) );
memset( judge , , sizeof( judge ) );
memset( location , , sizeof( location ) );
scanf("%d%d",&n,&m);
for( int i = ; i <= m ; i ++ )
{
scanf("%d%d",&a,&b);
if(judge[ a ][ b ] > ) continue; //判重。
judge[ a ][ b ] = ;
digree [ a ] ++;
}
a = topsort();
if( a ) {
int i = ;
for( ; i < n ; printf("%d ",location[ i++ ]) );
printf("%d\n",location[ i ]);
} else printf("-1\n");
}
return ;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141928.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站