从源到每一个人连一条容量为 (1) 的边。
从每一个导师到汇连一条容量为导师战队人数的边。
第一问我们依次枚举每一个学员，然后再依次与第 (1)至 (m) 志愿的老师连边，如果与第 (i) 志愿的导师连边跑最大流使得最大流改变，说明找到了一个导师与自己对应。自己的最小的能实现的志愿就是 (i) 。如果找不到志愿i的导师要把与志愿i的导师连的边删掉。不删听说会T，一开始以为要推流，结果并不用。。。
第二问，我们可以二分需要高多少名。然后跟第一问做一样的操作就行。但是我们需要知道处理完前 (i) 个学员的图是什么样子的。
所以要用可持久化网络流？？
因为数据范围很小，我们可以直接把处理完第i个学员后的图暴力存下。。。
然后这道题就解决了？
还有代码要写
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int INF=1e9;
const int N=205;
struct edge{
int to,nxt,flow;
}e[N*2+N*N*2],hise[N][N*2+N*N*2];
int cnt,head[N*2],hiscnt[N],hishead[N][N*2];
void add_edge(int u,int v,int flow){
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
e[cnt].flow=flow;
head[u]=cnt;
cnt++;
e[cnt].nxt=head[v];
e[cnt].to=u;
e[cnt].flow=0;
head[v]=cnt;
}
int dis[N*2];
bool bfs(int S,int T){
memset(dis,-1,sizeof(dis));
queue<int> q;
q.push(S);
dis[S]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]==-1&&e[i].flow){
dis[v]=dis[u]+1;
q.push(v);
}
}
}
if(dis[T]==-1)return false;
return true;
}
int dfs(int u,int T,int f){
if(u==T||f==0)return f;
int used=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]==dis[u]+1&&e[i].flow){
int w=dfs(v,T,min(e[i].flow,f-used));
if(w){
e[i].flow-=w;
e[i^1].flow+=w;
used+=w;
if(used==f)return f;
}
}
}
if(used==0)dis[u]=-1;
return used;
}
int ans,hisans[N];
void Dinic(int S,int T){
while(bfs(S,T))ans+=dfs(S,T,INF);
}
int S,T;
void Copy(int now){
for(int i=2;i<=cnt;i++)hise[now][i]=e[i];
hiscnt[now]=cnt;
for(int i=S;i<=T;i++)hishead[now][i]=head[i];
hisans[now]=ans;
}
vector<int> vec[N][N];
int s[N];
int n,m;
bool judge(int now,int pre){
for(int i=S;i<=T;i++)head[i]=hishead[pre][i];
cnt=hiscnt[pre];
for(int i=2;i<=hiscnt[pre];i++)e[i]=hise[pre][i];
ans=0;
for(int i=1;i<=s[now];i++){
if(vec[now][i].size()==0)continue;
for(int j=0;j<vec[now][i].size();j++)
add_edge(now,n+vec[now][i][j],1);
}
Dinic(S,T);
if(ans==1)return true;
return false;
}
int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return sum*f;
}
int tmp[N];
int main(){
int t=read(),C=read();
while(t--){
cnt=1;memset(head,0,sizeof(head));
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
vec[i][j].clear();
n=read();m=read();
S=0,T=n+m+1;
for(int i=1;i<=m;i++){
int w=read();
add_edge(i+n,T,w);
}
for(int i=1;i<=n;i++){
add_edge(S,i,1);
for(int j=1;j<=m;j++)
vec[i][read()].push_back(j);
}
for(int i=1;i<=n;i++)s[i]=read();
Copy(0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vec[i][j].size()==0)continue;
for(int k=0;k<vec[i][j].size();k++)
add_edge(i,n+vec[i][j][k],1);
ans=0;
Dinic(S,T);
if(ans==1){
tmp[i]=j;Copy(i);break;
}
for(int k=vec[i][j].size()-1;k>=0;k--){
int u=i,v=n+vec[i][j][k];
if(bfs(u,v)==0)Dinic(T,v),Dinic(u,S);
head[u]=e[head[u]].nxt;
head[v]=e[head[v]].nxt;
cnt-=2;
Dinic(S,T);
}
}
if(tmp[i]==0)Copy(i),tmp[i]=m+1;
}
for(int i=1;i<=n;i++)printf("%d ",tmp[i]);
printf("
");
for(int i=1;i<=n;i++){
if(tmp[i]<=s[i]){printf("0 ");continue;}
int l=1,r=i-1;
int Ans=i;
while(l<=r){
int mid=(l+r)>>1;
if(judge(i,i-mid-1))Ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d ",Ans);
}
printf("
");
}
return 0;
}