题目：这里 题意：软件在安装之后需要重启才能发挥作用，现在给你一堆软件(有的需要重启有的不需要)以及安装这个软件之前需要哪些软件发挥作用，求最少的重启次数。 解法：真拓扑好题，但是我不会。然后这个题有两种解法，解法1来自斌神：普通的拓扑排序用了一个队列，而现在用两个队列q1，q2分别来存 不需要重启的software 和 需要重启的software。根据题目输入建好图后，按照拓扑序规则，首先将入度的0的点加进队列，当然不需要重启的进q1，需要的进q2。然后处理q1中的所有节点（即要删除这些点），那么要让与他们相连的节点的入度减1，如果发现减完入度为0，再判断其是否需要重启，并加进q1 or q2。一旦发现q1为空，那么使答案加1（即重启一次），把q2中所有元素加入q1，q2清空。如此循环直到q1，q2均为空即可。
//HDU 5098 topsort #include <bits/stdc++.h> using namespace std; const int maxn = 1020; map <string, int> mp; int cnt, edgecnt, reboot[maxn], out[maxn], in[maxn]; int head[maxn], vis[maxn]; struct edge{ int v, nxt; edge(){} edge(int v, int nxt) : v(v), nxt(nxt) {} }E[maxn*maxn]; void init(){ edgecnt = cnt = 0; mp.clear(); memset(head, -1, sizeof(head)); memset(reboot, 0, sizeof(reboot)); memset(out, 0, sizeof(out)); memset(in, 0, sizeof(in)); } void addedge(int u, int v){ E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++; } int topsort(){ queue <int> q1, q2; for(int i = 1; i <= cnt; i++){ if(in[i] == 0){ if(reboot[i] == 0) q1.push(i); else q2.push(i); } } int ans = 0; while(!q1.empty() || !q2.empty()){ if(q1.empty() && !q2.empty()){ ans++; while(!q2.empty()){ q1.push(q2.front()); q2.pop(); } } while(!q1.empty()){ int u = q1.front(); q1.pop(); for(int i = head[u]; ~i; i = E[i].nxt){ int v = E[i].v; in[v]--; if(in[v] == 0){ if(reboot[v] == 0) q1.push(v); else q2.push(v); } } } } return ans; } int main() { string s; char name[1010]; int T, ks = 0; scanf("%d", &T); getchar(); getchar(); while(T--){ init(); printf("Case %d: ", ++ks); while(getline(cin, s)){ if(s[0] == '\0') break; istringstream sin(s); sin >> name; int len = strlen(name); int flag = 0; if(name[len - 2] == '*'){ flag = 1; name[len - 2] = '\0'; } else{ name[len - 1] = '\0'; } string a, b; a = name; if(mp.find(a) == mp.end()) mp[a] = ++cnt; reboot[mp[a]] = flag; while(sin >> b){ if(mp.find(b) == mp.end()) mp[b] = ++cnt; addedge(mp[b], mp[a]); out[mp[b]]++; in[mp[a]]++; } } int ans = topsort(); printf("%d\n", ans); } return 0; }解法2来自hdu鸟神：建图同上，在建完的DAG图中求最长路，然后需要重启的点权为1，不需要的为0。这样找出最长路的权和即可。易证：只有具有从属关系的重启需要分别进行，不然可以同时搞掉。这样需要对每个入度为0的点求一次这样的最长路，取最大值即可，具体方法用DP可解。真orz。
//HDU 5098 topsort #include <bits/stdc++.h> using namespace std; const int maxn = 1020; map <string, int> mp; int cnt, edgecnt, reboot[maxn], out[maxn], in[maxn]; int head[maxn], vis[maxn], dp[maxn]; struct edge{ int v, nxt; edge(){} edge(int v, int nxt) : v(v), nxt(nxt) {} }E[maxn*maxn]; void init(){ edgecnt = cnt = 0; mp.clear(); memset(head, -1, sizeof(head)); memset(reboot, 0, sizeof(reboot)); memset(out, 0, sizeof(out)); memset(in, 0, sizeof(in)); } void addedge(int u, int v){ E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++; } int dfs(int u){ if(dp[u]) return dp[u]; int ans = 0; for(int i = head[u]; ~i; i = E[i].nxt){ int v = E[i].v; ans = max(ans, dfs(v)); } return dp[u] = ans + reboot[u]; } int DAGdp(){ int ans = 0; memset(dp, 0, sizeof(dp)); for(int i = 1; i <= cnt; i++){ if(in[i] == 0){ ans = max(ans, dfs(i)); } } return ans; } int main() { string s; char name[1010]; int T, ks = 0; scanf("%d", &T); getchar(); getchar(); while(T--){ init(); printf("Case %d: ", ++ks); while(getline(cin, s)){ if(s[0] == '\0') break; istringstream sin(s); sin >> name; int len = strlen(name); int flag = 0; if(name[len - 2] == '*'){ flag = 1; name[len - 2] = '\0'; } else{ name[len - 1] = '\0'; } string a, b; a = name; if(mp.find(a) == mp.end()) mp[a] = ++cnt; reboot[mp[a]] = flag; while(sin >> b){ if(mp.find(b) == mp.end()) mp[b] = ++cnt; addedge(mp[b], mp[a]); out[mp[b]]++; in[mp[a]]++; } } int ans = DAGdp(); printf("%d\n", ans); } return 0; }