Labeling Balls(poj 3687)
2024-08-26 11:06:42
题意:N个球,从1~N编号,质量不同,范围1~N,无重复。给出小球间的质量关系(<), 要求给每个球贴标签,标签表示每个球的质量。按编号输出每个球的标签。如果解不唯一,按编号小的质量小排。
/*
被这道题坑惨了,刚开始读错题了,题目要求输出每个球的重量,而不是按重量输出球的编号
还有,因为题目要求如果有多解,则编号小的质量小,因为拓扑排序是按质量从小到大来找,
所以没有什么好的方法,于是反向拓扑,并且倒着找,把质量大的留给编号大的就可以了。
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 210
#define M 40010
using namespace std;
int head[N],out[N],vis[N],a[N],n,m;
struct node
{
int v,pre;
};node e[M];
void add(int i,int x,int y)
{
e[i].v=y;
e[i].pre=head[x];
head[x]=i;
}
void work()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(i,y,x);out[x]++;
}
int tot=n;
while()
{
int k=;
for(int i=n;i>=;i--)
if(!out[i]&&!vis[i])
{
a[i]=tot--;
vis[i]=;
k=i;
break;
}
if(!k)break;
for(int i=head[k];i;i=e[i].pre)
if(out[e[i].v])out[e[i].v]--;
}
if(tot)printf("-1");
else
for(int i=;i<=n;i++)
printf("%d ",a[i]);
printf("\n");
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(e,,sizeof(e));
memset(head,,sizeof(head));
memset(out,,sizeof(out));
memset(vis,,sizeof(vis));
work();
}
return ;
}
最新文章
- lightBox灯箱效果
- 实用的Scala泛函编程
- [转] Android Volley完全解析(一),初识Volley的基本用法
- WindowsApi 解压缩文件
- [Javascript] 面向对象编程思想
- Winfrom 抓取web页面内容代码
- hdu 5428 The Factor 分解质因数
- When does layoutSubviews get called?
- windows内存管理方式以及优缺点
- JavaScript高级程序设计 - 阅读笔记
- ●BZOJ 4237 稻草人
- matlab学习日志之并行运算
- 测试连接失败,因为初始化提供程序时发生错误,[DBNMPNTW] ConnectionOpen (CreateFile())
- AS使用自带虚拟机报错解决
- 利用React Native 从0到1 开发一款兼容IOS和android的APP(仿造京东)
- President&#39;s Office
- WCF 服务应用程序与 服务库之间的区别
- eclipse 在weblogic部署的工程项目开启远程调试remote config eclipse远程调试配置
- Word TOC域的使用说明
- ClientViaBehavior行为
热门文章
- 数组声明的几种方式以及length属性
- sed简单脚本练习
- VMware Workstation安装CentOS 7和开发环境
- 11 DOM基础
- 最新WIN10系统32位和64位纯净版自动激活版1010074 V2015年
- 【译】x86程序员手册33-9.6中断任务和中断处理程序
- MAC加域重复跳出---";talagent";想使用“本地项目” 的钥匙串
- Python_高阶函数、装饰器(decorator)
- mathAge.call(btn) 函数call 改变函数内 this #js
- 如何优化LIMIT