本文共 2676 字，大约阅读时间需要 8 分钟。
1 /* 2 双拓扑排序：抄的，以后来补 3 详细解释：http://blog.csdn.net/u012774187/article/details/40736995 4 */ 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 using namespace std; 19 20 #define lson l, mid, rt << 1 21 #define rson mid + 1, r, rt << 1 | 1 22 typedef long long ll; 23 24 const int MAXN = 1e3 + 10; 25 const int INF = 0x3f3f3f3f; 26 const double PI = acos (-1.0); 27 const double EPS = 1e-9; 28 struct Edge 29 { 30 int v, nxt; 31 }e[MAXN * MAXN]; 32 int in[MAXN], out[MAXN]; 33 int re[MAXN], head[MAXN]; 34 bool vis[MAXN]; 35 map M; 36 vector G[MAXN]; 37 int ecnt, cnt; 38 39 int TopoSort(void) 40 { 41 queue Q1, Q2; //Q1 !re Q2 re 42 for (int i=1; i<=cnt; ++i) 43 { 44 if (!in[i]) 45 { 46 if (!re[i]) Q1.push (i); 47 else Q2.push (i); 48 } 49 } 50 51 int ans = 0; 52 while (!Q1.empty () || !Q2.empty ()) 53 { 54 if (Q1.empty () && !Q2.empty ()) //重启 55 { 56 ans++; 57 while (!Q2.empty ()) //所有都重启安装 58 { 59 Q1.push (Q2.front ()); Q2.pop (); 60 } 61 } 62 while (!Q1.empty ()) 63 { 64 int u = Q1.front (); Q1.pop (); 65 vis[u] = true; 66 for (int i=head[u]; i!=-1; i=e[i].nxt) 67 { 68 int v = e[i].v; 69 if (!(--in[v])) 70 { 71 if (!re[v]) Q1.push (v); 72 else Q2.push (v); 73 } 74 } 75 } 76 } 77 78 return ans; 79 } 80 81 void init(void) 82 { 83 M.clear (); 84 ecnt = cnt = 0; 85 memset (in, 0, sizeof (in)); 86 memset (out, 0, sizeof (out)); 87 memset (re, 0, sizeof (re)); 88 memset (head, -1, sizeof (head)); 89 memset (vis, false, sizeof (vis)); 90 } 91 92 void add_edge(int u, int v) 93 { 94 e[ecnt].nxt = head[u]; 95 e[ecnt].v = v; 96 head[u] = ecnt++; 97 } 98 99 int main(void) //HDOJ 5098 Smart Software Installer100 {101 //freopen ("I.in", "r", stdin);102 103 string s;104 char name[1050];105 int n, cas = 0; scanf ("%d", &n); getchar (); getchar ();106 while (n--)107 {108 init ();109 while (getline (cin, s))110 {111 if (s[0] == '\0') break;112 istringstream sin (s);113 sin >> name;114 int len = strlen (name); int flag = 0;115 if (name[len-2] == '*') {flag = 1; name[len-2] = '\0';}116 else name[len-1] = '\0';117 118 string u = name, v;119 if (M.find (u) == M.end ())120 M[u] = ++cnt;121 re[M[u]] = flag;122 123 while (sin >> v)124 {125 if (M.find (v) == M.end ())126 M[v] = ++cnt;127 add_edge (M[v], M[u]);128 out[M[v]]++;129 in[M[u]]++;130 }131 }132 printf ("Case %d: %d\n", ++cas, TopoSort ());133 }134 135 return 0;136 }137 138 /*139 Case 1: 1140 Case 2: 2141 */
转载于:https://www.cnblogs.com/Running-Time/p/4523295.html