首页 > 代码库 > CERC 2012 J (拓扑排序)

CERC 2012 J (拓扑排序)

2024-07-10 10:09:50   225人阅读

题意：一些具有拓扑序的节点需要染色，这些节点一共分为两类。问你按照给出的拓扑顺序染色完结点最少需要多少次切换。

思路：我们按照拓扑排序的做法，建立两个栈分别存放两种不同种类的节点，每次把一个栈中的所有节点都处理完了才处理另一个，这样切换次数即为最终答案。

代码如下：

  1 /**************************************************  2  * Author     : xiaohao Z  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/  4  * Last modified : 2014-06-30 12:30  5  * Filename     : cerc_j.cpp  6  * Description     :   7  * ************************************************/  8   9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22  23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30  31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 100000+10; 34 int n, m, vex[LEN], ind[LEN], tmp_ind[LEN]; 35 bool vis[LEN]; 36 struct E{ 37     int to, next; 38 }edge[LEN*10]; 39 int head[LEN], top; 40  41 void init(){ 42     top = 0; 43     memset(head, -1, sizeof head); 44 } 45  46 void addedge(int u, int v){ 47     edge[top].next = head[u]; 48     edge[top].to = v; 49     head[u] = top++; 50 } 51  52 int solve(int flag){ 53     for(int i=0; i<n; i++) 54         ind[i] = tmp_ind[i]; 55     memset(vis, 0, sizeof vis); 56     queue<int> q1, q0; 57     for(int i=0; i<n; i++){ 58         if(!ind[i]){ 59             vis[i] = 1; 60             if(!vex[i]) q0.push(i); 61             else q1.push(i); 62         } 63     } 64     int ret = 0, cnt = 0; 65     for(;;ret++){ 66         if(flag){ 67             if(q1.empty()) { 68                 ret--; break; 69             } 70             while(!q1.empty()){ 71                 int nv = q1.front(); q1.pop(); 72                 cnt ++; 73                 for(int i=head[nv]; i!=-1; i=edge[i].next){ 74                     int nx = edge[i].to; 75                     ind[nx] --; 76                     if(!ind[nx] && !vis[nx]){ 77                         vis[nx] = 1; 78                         if(vex[nx]) q1.push(nx); 79                         else q0.push(nx); 80                     } 81                 } 82             } 83         }else{ 84             if(q0.empty()) { 85                 ret--; break; 86             } 87             while(!q0.empty()){ 88                 int nv = q0.front(); q0.pop(); 89                 cnt ++; 90                 for(int i=head[nv]; i!=-1; i=edge[i].next){ 91                     int nx = edge[i].to; 92                     ind[nx] --; 93                     if(!ind[nx] && !vis[nx]){ 94                         vis[nx] = 1; 95                         if(vex[nx]) q1.push(nx); 96                         else q0.push(nx); 97                     } 98                 } 99             }100         }101         flag = !flag;102     }103     if(cnt != n) return INF;104     return ret;105 }106 107 int main()108 {109 //    freopen("in.txt", "r", stdin);110 111     int a, b, T;112     scanf("%d", &T);113     while(T--){114         init();115         memset(tmp_ind, 0, sizeof tmp_ind);116         scanf("%d%d", &n, &m);117         for(int i=0; i<n; i++){118             scanf("%d", &vex[i]);119             vex[i] --;120         }121         for(int i=0; i<m; i++){122             scanf("%d%d", &a, &b);123             a--, b--;124             addedge(a, b);125             tmp_ind[b] ++;126         }127         int ans = min(solve(0), solve(1));128         printf("%d\n", ans);129     }130     return 0;131 }
View Code

 


联系
我们