?

題目傳送門

1 /* 2 雙拓?fù)渑判?#xff1a;抄的，以后來補 3 詳細(xì)解釋：http://blog.csdn.net/u012774187/article/details/40736995 4 */ 5 #include <cstdio> 6 #include <algorithm> 7 #include <iostream> 8 #include <sstream> 9 #include <cstring> 10 #include <cmath> 11 #include <string> 12 #include <vector> 13 #include <queue> 14 #include <map> 15 #include <set> 16 #include <ctime> 17 #include <cstdlib> 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<string, int> M; 36 vector<int> G[MAXN]; 37 int ecnt, cnt; 38 39 int TopoSort(void) 40 { 41 queue<int> 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 Installer 100 { 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: 1 140 Case 2: 2 141 */

?

轉(zhuǎn)載于:https://www.cnblogs.com/Running-Time/p/4523295.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的双拓扑排序 HDOJ 5098 Smart Software Installer的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。