逃生
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 604 Accepted Submission(s): 159
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
1 5 10 3 5 1 4 2 5 1 2 3 4 1 4 2 3 1 5 3 5 1 2
Sample Output
1 2 3 4 5
思路：拓扑排序。逆向建图。
先贴vector + priority_queue 的代码。 跑了 296ms c++
1 /*====================================================================== 2 * Author : kevin 3 * Filename : 逃生.cpp 4 * Creat time : 2014-07-20 19:03 5 * Description : 6 ========================================================================*/ 7 #include8 #include 9 #include 10 #include 11 #include 12 #include 13 #define clr(a,b) memset(a,b,sizeof(a))14 #define M 3000515 using namespace std;16 int in[M],ans[M];17 vector vec[M];18 void slove(int n)19 {20 priority_queue que;21 for(int i = 1; i <= n; i++){22 if(in[i] == 0) {23 que.push(i);24 }25 }26 int cnt = n;27 while(!que.empty()){28 int t = que.top();29 ans[--cnt] = t;30 que.pop();31 int len = vec[t].size();32 for(int i = 0; i < len; i++){33 if(--in[vec[t][i]] == 0){34 que.push(vec[t][i]);35 }36 }37 }38 int flag = 0;39 for(int i = 0; i < n; i++){40 if(!flag){41 printf("%d",ans[i]);42 flag = 1;43 }44 else{45 printf(" %d",ans[i]);46 }47 }48 }49 int main(int argc,char *argv[])50 {51 int t;52 scanf("%d",&t);53 while(t--){54 int n,m;55 scanf("%d%d",&n,&m);56 int a,b;57 clr(in,0);58 for(int i = 0; i < m; i++){59 scanf("%d%d",&a,&b);60 vec[b].push_back(a);61 in[a]++;62 }63 slove(n);64 printf("\n");65 for(int i = 0; i < M; i++){66 vec[i].clear();67 }68 }69 return 0;70 }
然后是链式前向星 + priority_queue。 跑了203ms c++
1 /*====================================================================== 2 * Author : kevin 3 * Filename : 逃生1.cpp 4 * Creat time : 2014-07-21 10:52 5 * Description : 6 ========================================================================*/ 7 #include8 #include 9 #include 10 #include 11 #include 12 #include 13 #define clr(a,b) memset(a,b,sizeof(a))14 #define M 30000515 using namespace std;16 int head[M],ans[M],in[M];17 struct Node18 {19 int to,next;20 };21 Node node[M];22 void AddEdges(int i,int j,int k)23 {24 node[k].to = j;25 node[k].next = head[i];26 head[i] = k;27 }28 void slove(int n)29 {30 priority_queue que;31 for(int i = 1; i <= n; i++){32 if(in[i] == 0)33 que.push(i);34 }35 int cnt = n,k;36 while(!que.empty()){37 int t = que.top();38 ans[--cnt] = t;39 que.pop();40 for(k = head[t]; k != -1; k = node[k].next){41 if(--in[node[k].to] == 0){42 que.push(node[k].to);43 }44 }45 }46 int flag = 0;47 for(int i = 0; i < n; i++){48 if(!flag){49 printf("%d",ans[i]);50 flag = 1;51 }52 else{53 printf(" %d",ans[i]);54 }55 }56 }57 int main(int argc,char *argv[])58 {59 int t;60 scanf("%d",&t);61 while(t--){62 int n,m;63 scanf("%d%d",&n,&m);64 int a,b;65 clr(in,0);66 clr(head,-1);67 int cnt = 1;68 for(int i = 0; i < m; i++){69 scanf("%d%d",&a,&b);70 AddEdges(b,a,cnt++);71 in[a]++;72 }73 slove(n);74 printf("\n");75 }76 return 0;77 }