分析：
这道题看题都看了我好久...
我们可以容易想到这道题和网络流有关。
首先，从原点向每个学员连一条流量为1的边
然后，要限制每个导师的学员，在每个导师连到汇点的时候流量限制为bi
再接着，按照学员的顺序一个个动态加边，一次性加入同样优先级的边，如果有增广路就记录答案。
（第一问完美解决）
然后第二问怎么做呢？
对于一个学员，如果已经确定了排位，那我们很容易的就能验证是不是满足他的要求。
那么我们就能在[1,i-1]的区间里二分答案去检验，在[1,now-1]的残余网络里面跑即可（注意加上他自己要求范围内的边）
如何优化？
第一问：如果把整个网络都加进去的话边数太多很可能会T，而我们发现有很多边是没用的->不能提供增广路的边
那我们在跑完一个优先级发现找不到增广路的时候就把这些边全删掉。
第二问：显然，二分答案每次都建立残余网络是一个很大的工程，我们可以在第一问依次处理时把残余网络图给存下来，第二问直接用即可。
Code
1 #include<bits/stdc++.h> 2 #define RG register int 3 #define rep(i,a,b) for(RG i=a;i<=b;++i) 4 #define per(i,a,b) for(RG i=a;i>=b;--i) 5 #define ll long long 6 #define inf (1<<29) 7 #define maxn 210 8 #define maxm 10010 9 using namespace std; 10 int p,c,n,m,cnt,S,T; 11 int tmph[maxn][maxn<<1],head[maxn<<1],hd[maxn<<1],step[maxn<<1],ans[maxn],cntt[maxn]; 12 int a[maxn][maxn],Ex[maxn],lmp[maxn][maxn],level[maxn],deal[maxn][maxn][12]; 13 struct E{ 14 int u,v,next,pre,fl; 15 }e[maxm],tmpe[maxn][maxm]; 16 17 inline int read() 18 { 19 int x=0,f=1;char c=getchar(); 20 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 21 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 22 return x*f; 23 } 24 25 void init() 26 { 27 memset(lmp,0,sizeof(lmp)); 28 memset(head,0,sizeof(head)); 29 cnt=1; 30 } 31 32 inline void del(int i) 33 { 34 if(e[i].next) e[e[i].next].pre=e[i].pre; 35 if(e[i].pre) e[e[i].pre].next=e[i].next; 36 if(i==head[e[i].u]) head[e[i].u]=e[i].next; 37 } 38 39 inline void add(int u,int v,int w) 40 { 41 e[++cnt].v=v,e[cnt].u=u,e[cnt].next=head[u]; 42 if(head[u]) e[head[u]].pre=cnt; 43 head[u]=cnt,e[cnt].fl=w; 44 45 swap(u,v); 46 47 e[++cnt].v=v,e[cnt].u=u,e[cnt].next=head[u]; 48 if(head[u]) e[head[u]].pre=cnt; 49 head[u]=cnt,e[cnt].fl=0; 50 } 51 52 inline void add2(int u,int v,int w) 53 { 54 e[++cnt].v=v,e[cnt].next=head[u],head[u]=cnt,e[cnt].fl=w; swap(u,v); 55 e[++cnt].v=v,e[cnt].next=head[u],head[u]=cnt,e[cnt].fl=0; 56 } 57 58 bool bfs() 59 { 60 queue<int> que; 61 memset(step,0,(T<<2)+5);memcpy(hd,head,(T<<2)+5); 62 que.push(S),step[S]=1; 63 RG u,v; 64 while(!que.empty()) 65 { 66 u=que.front(),que.pop(); 67 for(RG i=head[u];i;i=e[i].next) 68 { 69 v=e[i].v; 70 if(e[i].fl&&!step[v]) step[v]=step[u]+1,que.push(v); 71 } 72 } 73 return step[T]; 74 } 75 76 int dfs(int u,int fl) 77 { 78 if(u==T) return fl; 79 int tp,tt=0; 80 for(RG &i=hd[u];i;i=e[i].next){ 81 int v=e[i].v; 82 if(e[i].fl&&step[v]==step[u]+1) 83 { 84 tp=dfs(e[i].v,min(e[i].fl,fl)); 85 tt+=tp; 86 e[i].fl-=tp; 87 e[i^1].fl+=tp; 88 if(tt==fl) return tt; 89 } 90 } 91 if(tt!=fl) step[u]=-1; 92 return tt; 93 } 94 95 void work1() 96 { 97 RG l; 98 rep(i,1,n) 99 { 100 ans[i]=m+1,add(S,i,1); 101 rep(j,1,m) 102 { 103 if(!lmp[i][j]) continue; 104 l=cnt; 105 rep(k,1,lmp[i][j]) add(i,deal[i][j][k]+n,1); 106 if(bfs()&&dfs(S,inf)) {ans[i]=j;break;} 107 else {rep(k,l,cnt) del(k);cnt=l;} 108 } 109 rep(j,1,T) tmph[i][j]=head[j]; 110 rep(j,2,cnt) tmpe[i][j]=e[j]; 111 cntt[i]=cnt; 112 } 113 rep(i,1,n) printf("%d ",ans[i]);puts(""); 114 } 115 116 bool judge(int u,int w) 117 { 118 cnt=cntt[w-1]; 119 rep(i,1,T) head[i]=tmph[w-1][i]; 120 rep(i,2,cnt) e[i]=tmpe[w-1][i]; 121 122 add(S,u,1); 123 124 rep(i,1,Ex[u]) 125 { 126 if(!lmp[u][i]) continue; 127 rep(j,1,lmp[u][i]) add2(u,deal[u][i][j]+n,1); 128 } 129 130 return (bfs()&&dfs(S,inf)); 131 } 132 133 void input() 134 { 135 n=read(),m=read(); 136 S=n+m+1,T=n+m+2; 137 rep(i,1,m) 138 { 139 level[i]=read(); 140 add(i+n,T,level[i]); 141 } 142 cntt[0]=cnt; 143 rep(i,2,cnt) tmpe[0][i]=e[i]; 144 rep(i,1,T) tmph[0][i]=head[i]; 145 rep(i,1,n) rep(j,1,m) 146 { 147 a[i][j]=read(); if(!a[i][j]) continue; 148 deal[i][a[i][j]][++lmp[i][a[i][j]]] = j; 149 } 150 rep(i,1,n) Ex[i]=read(); 151 } 152 153 void work2() 154 { 155 RG l,r,mid,ans2; 156 rep(i,1,n) 157 { 158 if(ans[i]<=Ex[i]){printf("0 ");continue;} 159 l=1,r=i-1,ans2=0; 160 while(l<=r) 161 { 162 mid=l+r>>1; 163 if(judge(i,mid)) ans2=mid,l=mid+1; 164 else r=mid-1; 165 } 166 printf("%d ",i-ans2); 167 } 168 puts(""); 169 } 170 171 172 173 int main() 174 { 175 freopen("mentor.in","r",stdin); 176 freopen("mentor.out","w",stdout); 177 int TT,C; 178 TT=read(),C=read(); 179 while(TT--) 180 { 181 init(); 182 input(); 183 work1(); 184 work2(); 185 } 186 return 0; 187 }