首页 > 代码库 > HDU4857——逃生(反向建图+拓扑排序)

HDU4857——逃生(反向建图+拓扑排序)

2024-07-14 07:27:25   230人阅读

逃生

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

　　题目大意：

　　　　中文

　　解题思路：

　　　　求有向图的拓扑序列，要求序号小的尽量在前。

　　　　反向建图+拓扑排序。

　　　　PS：最多有3W个顶点，10W个边，邻接矩阵+普通拓扑时间空间都会超。

　　　　用邻接表或者链式前向星存图，优先队列进行拓扑。

Code：

 1 /*邻接表+优先队列*/ 2 #include<stdio.h> 3 #include<iostream> 4 #include<cstring> 5 #include<queue> 6 #define MAXN 300050 7 using namespace std; 8 int begin[MAXN],end[MAXN]; 9 int dis[MAXN],first[MAXN],next[MAXN];10 int N,M,topo[MAXN];11 bool vis[MAXN];12 void init()13 {14     memset(vis,0,sizeof(vis));15     memset(dis,0,sizeof(dis));16     memset(first,-1,sizeof(first));17 }18 void input()19 {20     cin>>N>>M;21     init();22     int k=1;23     for (int i=1; i<=M; i++)24     {25         int x1,x2;26         scanf("%d %d",&x2,&x1);27         int z=first[x1];28         begin[k]=x1,end[k]=x2;29         next[k]=first[begin[k]];30         first[begin[k]]=k;31         dis[x2]++;32         k++;33     }34 }35 void solve()36 {37     priority_queue<int> que;38     for (int i=1;i<=N;i++)39         if (dis[i]==0)40             que.push(i);41     int p=N+1;42     while (!que.empty())43     {44         int tmp=que.top();45         que.pop();46         topo[--p]=tmp;47         int z=first[tmp];48         while (z!=-1)49         {50             dis[end[z]]--;51             if(!dis[end[z]]) que.push(end[z]);52             z=next[z];53         }54     }55     /*for (int i=N; i>=1; i--) //超时56     {57         int j;58         for (j=N; j>=1; j--)59             if (!dis[j]&&!vis[j])60             {61                 topo[i]=j;62                 vis[j]=1;63                 break;64             }65         int z=first[j];66         while (z!=-1)67         {68                 dis[end[z]]--;69             z=next[z];70         }71     }*/72 }73 void output()74 {75     for (int i=1; i<=N; i++)76     {77         printf("%d",topo[i]);78         if (i==N) printf("\n");79         else printf(" ");80     }81 }82 int main()83 {84     int T;85     cin>>T;86     while (T--)87     {88         input();89         solve();90         output();91     }92     return 0;93 }

 

　　　　


联系
我们