Gym - 102307G Graduation
题意：xjl得修够n门课才能毕业，其中有些课是某门课的先行课，并且他精力有限，每学期最多只能修k门课，问xjl最少需要多少学期才能毕业。
首先，正向的图是n对1的，一个点会受到多个点的限制，所以反向建图，这样每去掉一个点，所释放的点都是没有限制的。
解法一：我们以原图中没有入度的点作为深度1，这样新图中没有人度的点就是最高深度，那么如果可以当前选择的点少于等于k个，直接便是取完这些点
那么当多于k个时，根据我们反向的原理自然是让深度高的选取。
1 #include<cstdio>
2 #include<vector>
3 #include<queue>
4 #include<algorithm>
5 using namespace std;
6 const int N=1e4+11;
7 struct Node{
8 int id,dep;
9 Node(){}
10 Node(int id,int dep):id(id),dep(dep){}
11 bool operator<(const Node& n1)const{
12 return dep<n1.dep;
13 }
14 };
15 int n,k,ne[N],ra[N];
16 vector<int> vv[N];
17 void dfs(int u){
18 if(vv[u].size()==0){
19 ra[u]=1;
20 return ;
21 }
22 for(int i=0;i<(int)vv[u].size();i++){
23 dfs(vv[u][i]);
24 ra[u]=max(ra[u],ra[vv[u][i]]+1);
25 }
26 }
27 int tp(){
28 queue<int> q;
29 priority_queue<Node> qq;
30 for(int i=1;i<=n;i++) if(!ne[i]) qq.push(Node(i,ra[i]));
31 int ans=0,cnt=0,u,v;
32 while(!qq.empty()){
33 ans++;
34 cnt=0;
35 while(!qq.empty()&&cnt<k){
36 cnt++;
37 q.push(qq.top().id);
38 qq.pop();
39 }
40 while(!q.empty()){
41 u=q.front();
42 q.pop();
43 for(int i=0;(int)i<vv[u].size();i++){
44 v=vv[u][i];
45 qq.push(Node(v,ra[v]));
46 }
47 }
48 }
49 return ans;
50 }
51 int main(){
52 while(~scanf("%d%d",&n,&k)){
53 for(int i=0;i<=n;i++) vv[i].clear();
54 for(int i=1;i<=n;i++){
55 scanf("%d",&ne[i]);
56 if(!ne[i]) continue;
57 vv[ne[i]].push_back(i);
58 }
59 for(int i=1;i<=n;i++) if(!ne[i]) dfs(i);
60 printf("%d\n",tp());
61 }
62 return 0;
63 }解法二：每门课的最快能学的学期就取决于它的深度,当某个课被提前学到了 就说明在它的之前可选择的课少于k个，此时直接让那些课便作为一层。
1 include<cstdio>
2 #include<vector>
3 #include<queue>
4 #include<algorithm>
5 using namespace std;
6 const int N=1e4+11;
7 int n,k,in[N],ne[N],ra[N];
8 vector<int> vv[N];
9 int tp(){
10 queue<int> q;
11 for(int i=1;i<=n;i++) if(!in[i]){
12 ra[i]=1;
13 q.push(i);
14 }
15 int ans=0,cnt=0,u,v;
16 while(!q.empty()){
17 u=q.front();
18 q.pop();
19 cnt++;
20 if(cnt==1) ans++;
21 if(cnt==k) cnt=0;
22 if(ra[u]>ans) ans++,cnt=1;
23 for(int i=0;i<(int)vv[u].size();i++){
24 v=vv[u][i];
25 ra[v]=max(ra[v],ra[u]+1);
26 in[v]--;
27 if(!in[v]) q.push(v);
28 }
29 }
30 return ans;
31 }
32 int main(){
33 while(~scanf("%d%d",&n,&k)){
34 for(int i=0;i<=n;i++){
35 in[i]=ra[i]=0;
36 vv[i].clear();
37 }
38 for(int i=1;i<=n;i++){
39 scanf("%d",&ne[i]);
40 if(!ne[i]) continue;
41 in[i]++;
42 vv[ne[i]].push_back(i);
43 }
44 printf("%d\n",tp());
45 }
46 return 0;
47 }
48 /*
49 4 2
50 4 4 4 0
51 */