第一问：

左边一列点代表学生，右边一列点代表导师

导师向汇点连流量为 人数限制的 边

然后从第一个学生的第一志愿往里面加边

如果当前学生的当前志愿可以满足，即目前网络流可以满流，保留这一志愿的边，然后下一个学生

否则，删除这一志愿的边，然后下一个志愿

第二问：

二分这个学生要前进多少名

假设是学生i要前进x名

把前i-x-1名的学生 在第一问中满足的志愿 的边加进去

在把学生i的边加进去

判断是否满流

注意判断满流的时候 不包括前i-x-1名学生里没有任何导师的学生

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define N 201#define M 80801 int n,m;int lim[N];int a[N][N][N];int cnt[N][N];int dream[N];int tot=1;int src,decc;int lev[N<<1],cur[N<<1];int front[M<<1],nxt[M<<1],to[M<<1],cap[M<<1];queue
          
           q;int st[N];inline void read(int &x){ x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}inline void init(){ read(n); read(m); decc=n+m+1; for(int i=1;i<=m;++i) read(lim[i]); int x; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { read(x); if(x) a[i][x][++cnt[i][x]]=j; } for(int i=1;i<=n;++i) read(dream[i]);}inline void add(int u,int v,int w){ to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=w; to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=0;}inline bool bfs(){ for(int i=0;i<=decc;++i) cur[i]=front[i],lev[i]=-1; while(!q.empty()) q.pop(); q.push(src); lev[src]=0; int now,t; while(!q.empty()) { now=q.front(); q.pop(); for(int i=front[now];i;i=nxt[i]) { t=to[i]; if(lev[t]==-1 && cap[i]) { lev[t]=lev[now]+1; if(t==decc) return true; q.push(t); } } } return false;}inline int dinic(int now,int flow){ if(now==decc) return flow; int rest=0,delta; for(int &i=cur[now];i;i=nxt[i]) if(cap[i] && lev[to[i]]==lev[now]+1) { delta=dinic(to[i],min(flow-rest,cap[i])); if(delta) { rest+=delta; cap[i]-=delta; cap[i^1]+=delta; if(rest==flow) break; } } if(rest!=flow) lev[now]=-1; return rest;}void solve1(){ for(int i=1;i<=m;++i) add(n+i,decc,lim[i]); int ok; for(int i=1;i<=n;++i) { add(src,i,1); for(int j=1;j<=m;++j) if(cnt[i][j]) { for(int k=1;k<=cnt[i][j];++k) add(i,n+a[i][j][k],1); if(bfs()) { dinic(src,i); st[i]=j; break; } else { for(int k=1,h=tot;k<=cnt[i][j];++k,h-=2) cap[h]=cap[h-1]=0; } } } for(int i=1;i<=n;++i) printf("%d ",st[i] ? st[i] : m+1); putchar('\n');}inline bool check(int x,int goal){ tot=1; memset(front,0,sizeof(front)); for(int i=1;i<=m;++i) add(n+i,decc,lim[i]); int ok=0; for(int i=1;i
           
            >1; if(check(i,i-mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%d ",ans); } putchar('\n');}void clear(){ memset(st,0,sizeof(st)); memset(cnt,0,sizeof(cnt)); memset(front,0,sizeof(front)); tot=1;}int main(){ //freopen("mentor.in","r",stdin); //freopen("mentor.out","w",stdout); int T,C; read(T); read(C); while(T--) { clear(); init(); solve1(); solve2(); }}