D - Ordering Tasks
题意:给个有向图,进行拓扑排序,也可使用BFS进行拓扑排序
1 /***********************************************/ 2 struct node{ 3 int v; 4 node(){} 5 node(int _v):v(_v){} 6 }; 7 vector<node>G[maxn];//邻接表法 8 int in[maxn],out[maxn];//每个顶点入度出度 9 int n,m; 10 11 void Tuop() 12 { 13 for(int i=1;i<=n;i++) 14 if(in[i]==0) 15 { 16 for(int j=0;j<G[i].size();j++) 17 { 18 in[G[i][j].v]--; 19 } 20 cout<<i<<" "; 21 in[i]=-1; 22 Tuop(); 23 break; 24 } 25 } 26 27 int main() 28 { 29 30 while(1) 31 { 32 sc2(n,m); 33 if(n==0 && m==0) return 0; 34 mem0(G); 35 mem0(in); 36 mem0(out); 37 for(int i=1;i<=m;i++){ 38 int a,b; 39 sc2(a,b); 40 G[a].push_back(node(b)); 41 in[b]++; 42 out[a]++; 43 } 44 45 Tuop(); 46 cout<<endl; 47 } 48 return 0; 49 } 50 51 52 /* 53 5 4 54 1 2 55 2 3 56 1 3 57 1 5 58 0 0 59 */
E - 确定比赛名次
一样的有向图拓扑排序,答案用vector存一下,保证空格
1 /***********************************************/ 2 struct node{ 3 int v; 4 node(){} 5 node(int _v):v(_v){} 6 }; 7 vector<int>ans;//存拓扑排序结果 8 vector<node>G[maxn];//邻接表法 9 int in[maxn],out[maxn];//每个顶点入度出度 10 int n,m; 11 12 void Tuop() 13 { 14 for(int i=1;i<=n;i++) 15 if(in[i]==0) 16 { 17 for(int j=0;j<G[i].size();j++) 18 { 19 in[G[i][j].v]--; 20 } 21 ans.p_b(i); 22 in[i]=-1; 23 Tuop(); 24 break; 25 } 26 } 27 28 int main() 29 { 30 while(sc2(n,m)!=EOF) 31 { 32 ans.clear(); 33 34 if(n==0 && m==0) return 0; 35 mem0(G); 36 mem0(in); 37 mem0(out); 38 for(int i=1;i<=m;i++){ 39 int a,b; 40 sc2(a,b); 41 G[a].push_back(node(b)); 42 in[b]++; 43 out[a]++; 44 } 45 Tuop(); 46 cout<<ans[0]; 47 for(int i=1;i<ans.size();i++) 48 cout<<" "<<ans[i]; 49 cout<<endl; 50 } 51 return 0; 52 } 53 54 55 /* 56 5 4 57 1 2 58 2 3 59 1 3 60 1 5 61 0 0 62 */
HDU 4857 (反向拓扑排序 + 优先队列)
逃生:
分析:
题目要求在满足拓扑的前提下,小序号需要先输出。可以先考虑1号节点,是1的父节点的一定是要在1的前边输出的,那么反向建边再反向输出答案肯定是满足拓扑关系的。想想为什么正向拓扑不行,因为对于1号节点,应该是最先考虑怎么把它输出的,但是如果正向拓扑就会考虑1号节点之前的点的优先顺序,比如1前边有一个最大值,那么1就成最后考虑的了。
---------------------
作者:_hehe_
来源:CSDN
原文:https://blog.csdn.net/wty__/article/details/38235961
F - 逃生
糟糕的事情发生啦,现在大家都忙着逃命。但是逃命的通道很窄,大家只能排成一行。
现在有n个人,从1标号到n。同时有一些奇怪的约束条件,每个都形如:a必须在b之前。
同时,社会是不平等的,这些人有的穷有的富。1号最富,2号第二富,以此类推。有钱人就贿赂负责人,所以他们有一些好处。
负责人现在可以安排大家排队的顺序,由于收了好处,所以他要让1号尽量靠前,如果此时还有多种情况,就再让2号尽量靠前,如果还有多种情况,就让3号尽量靠前,以此类推。
那么你就要安排大家的顺序。我们保证一定有解。
现在有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
题解:必须反向拓扑(即从出度为0的点开始,构建逆向图),使用优先队列(priority_queue 优先队列)每次取最大,最后将答案逆序打印
此拓扑排序类似与BFS,将待选项加入queue
至于为什么正向拓扑不行...挖个坑,以后想到填......
1 /***********************************************/ 2 struct node{ 3 int v; 4 node(){} 5 node(int _v):v(_v){} 6 }; 7 vector<int>V; 8 vector<node>G[maxn];//邻接表法 9 int in[maxn],out[maxn];//每个顶点入度出度 10 int n,m; 11 12 void Tuop()//BFS解法 13 { 14 //priority_queue <int,vector<int>,greater<int> > Q;//优先队列 15 priority_queue<int>Q; 16 for(int i=1;i<=n;i++) if(out[i]==0) Q.push(i); 17 int p;//从出度为0的点开始 18 while(!Q.empty()) 19 { 20 p=Q.top(); 21 V.p_b(p); 22 Q.pop(); 23 for(int i=0;i<G[p].size();i++) 24 { 25 out[G[p][i].v]--; 26 if(out[G[p][i].v]==0) Q.push(G[p][i].v); 27 } 28 } 29 } 30 31 int mp[maxn]; 32 33 int main() 34 { 35 int t; 36 sc(t); 37 38 while(t--) 39 { 40 V.clear(); 41 sc2(n,m); 42 mem0(G); 43 mem0(out); 44 mem0(mp); 45 for(int i=1;i<=m;i++){ 46 int a,b; 47 sc2(a,b); 48 if(mp[a]!=b){ 49 G[b].push_back(node(a));//构建逆向图 50 mp[a]=b; 51 out[a]++; 52 } 53 } 54 Tuop(); 55 cout<<V[V.size()-1]; 56 for(int i=V.size()-2;i>=0;i--) cout<<" "<<V[i]; 57 cout<<endl; 58 } 59 return 0; 60 }
......