首页 > 代码库 > UVALive 6264 Conservation --拓扑排序
UVALive 6264 Conservation --拓扑排序
题意：一个展览有n个步骤，告诉你每一步在那个场馆举行，总共2个场馆，跨越场馆需要1单位时间，先给你一些约束关系，比如步骤a要在b前执行，问最少的转移时间是多少。
解法：根据这些约束关系可以建立有向边，可以看出是拓扑排序问题，问题是怎样拓扑排序。
进行两次拓扑排序，分别建立两个集合，一个放场馆1举行的步骤，一个放场馆2的，然后第一次从场馆1开始进行拓扑排序，每次一个场馆取完后看另一个场馆是否有步骤要执行，有则执行，然后将度数变为0的压入队列，如此往复。第二次从场馆2开始进行。得出的最小值为答案。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <queue>using namespace std;#define N 100007int in[N],co[N],tin[N];vector<int> G[N];int min(int ka,int kb){ if(ka < kb) return ka; return kb;}int main(){ int t,n,m,i,j,u,v; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&co[i]); G[i].clear(); } memset(in,0,sizeof(in)); while(m--) { scanf("%d%d",&u,&v); G[u].push_back(v); in[v]++; } for(i=1;i<=n;i++) tin[i] = in[i]; int sum = 0; queue<int> que[2]; int tot = 2; int ans = Mod; while(tot--) { int cnt = 0; int now = tot; for(i=1;i<=n;i++) in[i] = tin[i]; for(i=1;i<=n;i++) { if(in[i] == 0) { if(co[i] == 1) que[0].push(i); else que[1].push(i); } } do { cnt++; while(!que[now].empty()) { int u = que[now].front(); que[now].pop(); for(i=0;i<G[u].size();i++) { int v = G[u][i]; in[v]--; if(in[v] == 0) { if(co[v] == 1) que[0].push(v); else que[1].push(v); } } } now = 1-now; }while(!que[now].empty()); //cout<<"cnt = "<<cnt<<endl; ans = min(ans,cnt); } printf("%d\n",ans-1); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。