sol
从前往后依次加边，每次对一个人做完劈配后就把当前这个残余网络存下来。这样第二问就可以二分排在第几名然后check一下在对应排名的残余网络上还能不能再增广。
给网络流开结构体直接赋值美滋滋。
然后这样就可以根据评测机的实际情况获得(60-80)不等的好成绩。
一个显而易见的优化就是：对于一个人，如果他已经确认了选择某个志愿，那么不仅更靠后的志愿是没用的，更靠前的志愿也是没用的。
所以对于一个人我们只需要保留他选的那个志愿对应的那至多(C)条边，这样边数和时间复杂度都降下来了。
按照上面的思路就可以成功通过本题了。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int inf = 1e9;
const int N = 405;
int n,m,S,T,a[N][N],b[N],id[N],s[N],ans[N];
queue<int>Q;
struct edge{int to,nxt,w;};
struct net{
edge a[N*30];
int head[N],cnt,dep[N],cur[N];
inline void init(){memset(head,0,sizeof(head));cnt=1;}
inline void link(int u,int v,int w)
{
a[++cnt]=(edge){v,head[u],w};head[u]=cnt;
a[++cnt]=(edge){u,head[v],0};head[v]=cnt;
}
inline bool bfs()
{
memset(dep,0,sizeof(dep));
dep[S]=1;Q.push(S);
while (!Q.empty())
{
int u=Q.front();Q.pop();
for (int e=head[u];e;e=a[e].nxt)
if (a[e].w&&!dep[a[e].to])
dep[a[e].to]=dep[u]+1,Q.push(a[e].to);
}
return dep[T];
}
int dfs(int u,int f)
{
if (u==T) return f;
for (int &e=cur[u];e;e=a[e].nxt)
if (a[e].w&&dep[a[e].to]==dep[u]+1)
{
int tmp=dfs(a[e].to,min(a[e].w,f));
if (tmp) {a[e].w-=tmp;a[e^1].w+=tmp;return tmp;}
}
return 0;
}
inline int dinic()
{
int res=0;
while (bfs())
{
for (int i=1;i<=T;++i) cur[i]=head[i];
while (int tmp=dfs(S,1)) res+=tmp;
}
return res;
}
}G[N>>1];
inline bool cmp(int i,int j){return b[i]<b[j];}
int main()
{
freopen("mentor.in","r",stdin);
freopen("mentor.out","w",stdout);
int Case=gi();gi();
while (Case--)
{
n=gi();m=gi();S=n+m+1;T=S+1;
G[0].init();
for (int i=1,x;i<=m;++i) x=gi(),G[0].link(i+n,T,x);
for (int i=1,j,res;i<=n;++i)
{
for (j=1;j<=m;++j) a[i][j]=b[j]=gi(),id[j]=j;
sort(id+1,id+m+1,cmp);
j=1;while (j<=m&&!b[id[j]]) ++j;
for (res=1;res<=m;++res)
{
G[i]=G[i-1];G[i].link(S,i,1);
while (j<=m&&b[id[j]]==res) G[i].link(i,id[j]+n,1),++j;
if (G[i].dinic()) break;
}
printf("%d ",ans[i]=res);
}
puts("");
for (int i=1;i<=n;++i)
{
s[i]=gi();
if (ans[i]<=s[i]) {printf("0 ");continue;}
int l=0,r=i-1,res=0;
while (l<=r)
{
int mid=l+r>>1;
net tmp=G[mid];tmp.link(S,i,1);
for (int j=1;j<=m;++j) if (a[i][j]&&a[i][j]<=s[i]) tmp.link(i,j+n,1);
if (tmp.dinic()) res=l=mid+1;else r=mid-1;
}
printf("%d ",i-res);
}
puts("");
}
return 0;
}