题目：https://www.luogu.org/problemnew/show/P4382
原本想着网络流。不过看了一番题解发现二分图匹配也行。
原本想着第一问也二分，不过看了一番题解发现一档一档地判断就行。不过不知道复杂度是怎样的。
原本想着第二问二分，把后面人的影响去掉的方法是在网络流里断掉源点连向后面人的边。不过看了一番题解发现用二分图匹配，把 n 个图都存下来，二分的时候在对应的图上做就行了。
数据范围小的话真是可以存很多东西来降低复杂度。自己应该拓宽思路。
二分图匹配的时候用 vector 记录每个导师已经匹配了哪些人；再记录该导师战队还剩下多少人（不用专门记也可，用原来的 b[ ] 减去 vector 的 size 即可），就能增广了。
重新认识了匈牙利算法。每次给对面的点打 vis 标记也是为了不让增广路径上的点匹配回原来的选择。
注意换导师的匹配的时候要把这个人从 vector 里删掉。用了那种 erase + remove 的方法。这个操作其实是线性的吧？感觉复杂度全靠信仰。不过竟然还跑得很快。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define pb push_back #define it per[cs[cr]] using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } const int N=205,M=15; int n,m,s[N]; bool vis[N]; int a[N][N][M],len[N][N]; struct Gra{ int b[N],c[N],cs[N]; vector<int> per[N]; bool xyl(int cr,int nw) { for(int i=1,v;i<=len[cr][nw];i++) if(!vis[v=a[cr][nw][i]]) { vis[v]=1; if(b[v]) { if(cs[cr]) { b[cs[cr]]++;// it.erase(remove(it.begin(),it.end(),cr));// } b[v]--;per[v].pb(cr); cs[cr]=v; c[cr]=nw; return true; } for(int j=0,lm=per[v].size();j<lm;j++) if(xyl(per[v][j],c[per[v][j]])) { if(cs[cr]) { b[cs[cr]]++; it.erase(remove(it.begin(),it.end(),cr));// } b[v]--;per[v].pb(cr); cs[cr]=v; c[cr]=nw; return true; } } return false; } void solve(int cr) { for(int i=1,lm;i<=m;i++) if(len[cr][i]) { memset(vis,0,sizeof vis); if(xyl(cr,i))break; } if(!c[cr])c[cr]=m+1; } }g[N],f; bool chk(int cr,int mid) { f=g[cr-mid-1]; for(int i=1;i<=s[cr];i++) { memset(vis,0,sizeof vis);// if(f.xyl(cr,i))return true; } return false; } int main() { int T=rdn(),C=rdn(); while(T--) { memset(len,0,sizeof len); n=rdn();m=rdn(); for(int i=1;i<=m;i++)g[0].b[i]=rdn(); for(int i=1,d;i<=n;i++) for(int j=1;j<=m;j++) { d=rdn();if(d)a[i][d][++len[i][d]]=j; } for(int i=1;i<=n;i++)s[i]=rdn(); for(int i=1;i<=n;i++) { g[i]=g[i-1]; g[i].solve(i);} for(int i=1;i<=n;i++) printf("%d ",g[i].c[i]);puts(""); for(int i=1;i<=n;i++) { if(g[i].c[i]<=s[i]) {printf("0 ");continue;} int l=1,r=i-1,ret=i; while(l<=r) { int mid=l+r>>1; if(chk(i,mid))ret=mid,r=mid-1; else l=mid+1; } printf("%d ",ret); } puts(""); } return 0; }