Labeling Balls--poj3687
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 12273 | Accepted: 3516 |
Description
Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that:
- No two balls share the same label.
- The labeling satisfies several constrains like "The ball labeled with a is lighter than the one labeled with b".
Can you help windy to find a solution?
Input
The first line of input is the number of test case. The first line of each test case contains two integers, N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ 40,000). The next M line each contain two integers a and b indicating the ball labeled with a must be lighter than the one labeled with b. (1 ≤ a, b ≤ N) There is a blank line before each test case.
Output
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... If no solution exists, output -1 instead.
Sample Input
5 4 0 4 1
1 1 4 2
1 2
2 1 4 1
2 1 4 1
3 2
Sample Output
1 2 3 4
-1
-1
2 1 3 4
1 3 2 4 这是一个拓扑题,还不是普通的拓扑,这必须要反向建图+逆向输出,并且注意,这个题让输出的是各个人的位置!!!
#include <iostream>
#include<cstdio>
#include<cstring> using namespace std;
int map[][];
int degree[];
void topo(int n)
{
int i,j,mark,que[];
for(i=n;i>=;i--)
{
int x=;//标记看是否满足要求
for(j=n;j>=;j--)
{
if(degree[j]==)
{
x=;
mark=j;
break;
}
}
if(x==)
break;
que[mark]=i;
degree[mark]=-;
for(j=;j<=n;j++)
{
if(map[mark][j])
degree[j]--;
}
}
if(i!=-)
printf("-1\n");
else
{
printf("%d",que[]);
for(i=;i<=n;i++)
printf(" %d",que[i]);
printf("\n"); }
} int main()
{
int N,i,m,n,a,b;
scanf("%d",&N);
while(N--)
{
memset(map,,sizeof(map));
memset(degree,,sizeof(degree));
scanf("%d%d",&n,&m);
for(i=;i<m;i++)
{
scanf("%d%d",&a,&b);
if(!map[b][a])//避免重复录入
{
map[b][a]=;
degree[a]++;//反向建图
}
}
topo(n);
}
return ;
}
最新文章
- .NET短距离领域通信-32feet.NET
- 负载均衡算法(四)IP Hash负载均衡算法
- OpenCascade HLR for Pipe Model
- SQL server 数据库备份还原Sql
- RedHat中敲sh-copy-id命令报错:-bash: ssh-copy-id: command not found
- php 解决和避免form表单重复提交的方法
- oc深坑測试题及其答案
- MySQL锁学习之UPDATE
- Hadoop之SequenceFile
- 一步一步创建ASP.NET MVC5程序[Repository+Autofac+Automapper+SqlSugar](九)
- 2017年PHP程序员未来路在何方——韩天峰
- Server-U FTP与AD完美集成方案详解
- vue日历控件,自定义选择年月 选择年月日 选择年月日时 选择年月日时分,自定义日期范围
- Oracle学习DayTwo
- Java IO浅析
- tmux 基本用法
- iptables综述
- 通过curl模拟多线程抓取网页(curl_multi_*)
- 数据库-Core Data
- mouseover 有一个多次触发的问题