设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

HDOJ 4857 逃生

2014-07-20 22:21:00.0 数据结构  
导读:BestHack.....真乱.....逃生Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 139    Accepted Submission(s): 20Problem Description糟糕的事情发生啦,现在大家都忙着逃命。但是逃...。。。

BestHack.....真乱.....

逃生

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 139    Accepted Submission(s): 20


Problem Description
糟糕的事情发生啦,现在大家都忙着逃命。但是逃命的通道很窄,大家只能排成一行。

现在有n个人,从1标号到n。同时有一些奇怪的约束条件,每个都形如:a必须在b之前。
同时,社会是不平等的,这些人有的穷有的富。1号最富,2号第二富,以此类推。有钱人就贿赂负责人,所以他们有一些好处。

负责人现在可以安排大家排队的顺序,由于收了好处,所以他要让1号尽量靠前,如果此时还有多种情况,就再让2号尽量靠前,如果还有多种情况,就让3号尽量靠前,以此类推。

那么你就要安排大家的顺序。我们保证一定有解。
 

Input
第一行一个整数T(1 <= T <= 5),表示测试数据的个数。
然后对于每个测试数据,第一行有两个整数n(1 <= n <= 30000)和m(1 <= m <= 100000),分别表示人数和约束的个数。

然后m行,每行两个整数a和b,表示有一个约束a号必须在b号之前。a和b必然不同。
 

Output
对每个测试数据,输出一行排队的顺序,用空格隔开。
 

Sample Input
15 103 51 42 51 23 41 42 31 53 51 2
 

Sample Output
1 2 3 4 5
 

Author
CLJ
 

Source
 



#include #include #include #include #include #include using namespace std;const int maxn=63000;int n,m;struct Edge{    int to,next;}edge[maxn*3];int Adj[maxn],Size=0,du[maxn];bool used[maxn];void Add_Edge(int u,int v){    edge[Size].to=v;    edge[Size].next=Adj[u];    du[v]++;    Adj[u]=Size++;}void init(){    memset(Adj,-1,sizeof(Adj));Size=0;    memset(du,0,sizeof(du));    memset(used,false,sizeof(used));}priority_queue,less > q;vector vc;int main(){    int T_T;    scanf("%d",&T_T);    while(T_T--)    {        init();        vc.clear();        scanf("%d%d",&n,&m);        for(int i=0;i=0;i--)        {            if(i!=sz-1) putchar(32);            printf("%d",vc[i]);        }        putchar(10);    }    return 0;}





(编辑: u012797220)

网友评论
相关文章