上面的算法可以看出来要很多次建图，又因为图最多只有 2n 的点和 nC 的边，那就可以暴力的存n 个图，分别对应前n 个人的最优方案的残余网络，这样可以大大减少建图浪费的时间，并且每次只需要单路增广。
用 vector 貌似会快一些？
复杂度 $O(不慢)$，第一问最多 nm 次找增广路，第二问 nlogn 次，及时删掉没用的边就不会 TLE 。
以上摘自题解
哇这种直接把一张图保存下来的奇技淫巧学到了啊，很强势
upd：再把 to 写成 flow 就剁手
Code
// By YoungNeal #include<queue> #include<vector> #include<cstdio> #include<cctype> #include<cstring> #include<iostream> #define N 505 int T,C; int n,m; int s,t; int maxn; int d[N]; int deg[N]; int ans[N]; int want[N]; int zhiyuan[205][205][205]; struct Edge{ int to,nxt,flow; }; struct Graph{ std::vector<Edge> edge[N]; void add(int x,int y,int z){ edge[x].push_back((Edge){y,edge[y].size(),z}); edge[y].push_back((Edge){x,edge[x].size()-1,0}); } void del(int x,int y){ edge[x].pop_back(); edge[y].pop_back(); } bool bfs(){ std::queue<int> q; q.push(s); memset(d,0,sizeof d); d[s]=1; while(q.size()){ int u=q.front();q.pop(); for(int i=0;i<edge[u].size();i++){ int to=edge[u][i].to; if(d[to]) continue; if(!edge[u][i].flow) continue; d[to]=d[u]+1; q.push(to); if(to==t) return 1; } } return 0; } int dinic(int now,int flow){ if(now==t) return flow; int rest=flow; for(int i=0;i<edge[now].size();i++){ if(!rest) return flow; int to=edge[now][i].to; if(!edge[now][i].flow) continue; if(d[to]!=d[now]+1) continue; int k=dinic(to,std::min(rest,edge[now][i].flow)); if(!k) d[to]=0; rest-=k; edge[now][i].flow-=k; edge[ edge[now][i].to ][ edge[now][i].nxt ].flow+=k; } return flow-rest; } void clear(){ for(int i=1;i<=n+m+2;i++) edge[i].clear(); } }G[N]; void clear(){ maxn=0; s=n+m+1; t=s+1; memset(zhiyuan,0,sizeof zhiyuan); for(int i=0;i<=n;i++) G[i].clear(); } void read(int &x){ x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); } bool check(int x,int now){ int gotonow=now-x; if(gotonow<1) return 0; Graph P; P=G[gotonow-1]; P.add(s,now,1); for(int i=1;i<=want[now];i++){ for(int j=1;j<=zhiyuan[now][i][0];j++) P.add(now,zhiyuan[now][i][j]+n,1); } return P.bfs(); } void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } signed main(){ read(T);read(C); while(T--){ read(n),read(m); clear(); for(int i=1;i<=m;i++) read(deg[i]),G[0].add(i+n,t,deg[i]); for(int i=1;i<=n;i++){ for(int x,j=1;j<=m;j++){ read(x); if(!x) continue; maxn=std::max(maxn,x); zhiyuan[i][x][++zhiyuan[i][x][0]]=j; } } for(int i=1;i<=n;i++) read(want[i]); for(int i=1;i<=n;i++){ bool o=0; G[i]=G[i-1]; G[i].add(s,i,1); for(int j=1;j<=maxn;j++){ if(!zhiyuan[i][j][0]) continue; for(int p=1;p<=zhiyuan[i][j][0];p++) G[i].add(i,zhiyuan[i][j][p]+n,1); if(G[i].bfs()){ G[i].dinic(s,0x3f3f3f3f); o=1,ans[i]=j,write(j),putchar(' '); } if(o) break; for(int p=1;p<=zhiyuan[i][j][0];p++) G[i].del(zhiyuan[i][j][p]+n,i); } if(!o) ans[i]=m+1,write(m+1),putchar(' '); } putchar('\n'); for(int i=1;i<=n;i++){ if(ans[i]<=want[i]){ write(0),putchar(' '); continue; } int now=-1; int l=1,r=i-1; while(l<=r){ int mid=l+r>>1; if(check(mid,i)) now=mid,r=mid-1; else l=mid+1; } if(now==-1) write(i),putchar(' '); else write(now),putchar(' '); } putchar('\n'); } return 0; }