碰到这种匹配的题
二分图匹配，网络流嘛
需要将选手按照排名从大倒小依次匹配，每个选手都是在上一个选手的残留网络上继续匹配
为了满足当前选手的最优匹配，需要从小到大按顺序枚举选手的志愿进行匹配
这样暴力建图匹配复杂度有点高，所以考虑二分，发现前i个志愿中有可以被录取的的，那更多的志愿一定可以被录取，是满足二分性的
这样可以找到一个人的最优志愿匹配，第一问ok
对于第二问，我们发现当一个人在一个排名可以满足期望值的时候，排名更靠前时一定更能满足
那么就可以二分，求出满足期望值要增加最少的排名
两次二分的建图方法是这样的
源点向学员连容量为1的边，导师向汇点连容量为战队人数限制容量的边，学员和其选择的导师间连容量为1的边
跑dinic，如果有流量，就表示能够匹配到
首先将这个人之前（第一问就是编号这个排名，第二问要用编号排名减去上升的名次）的人的最优录取志愿中的导师加到图当中，这样保证之前的人匹配到的志愿依旧是满足前几个人的最优匹配的
因为每个志愿选择的导师不会超过C个（C<=10），可以保证建图的复杂度
（这个地方刚开始我是将所有志愿全都加进去，后来发现是不对的，并不能保证是最优的），然后跑一遍dinic，在残余网络上进行这个人的匹配
这个人进行匹配时，第一问要将二分的志愿之前的所有志愿加到图中，第二问要将这个人最低期望录取志愿之前的所有志愿加到图中，跑一遍dinic
可以发现，这样一共会跑O(nlogn)次dinic，时间复杂度是可以接受的
注意点：我是用二维的vector存储每个人每个志愿想要选择的导师的，每组数据之前一定要保证完全清空（每组数据的最后将vector清空），否则会出问题的，因为这个debug了好久
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> using namespace std; typedef long long ll; const int maxn = 2010; const int INF = 1e9+7; int T,C,n,m,s,t; int b[maxn],a[maxn][maxn],S[maxn]; int res1[maxn],res2[maxn]; vector<int> v[maxn][maxn]; int h[maxn],size=1; struct E{ int to,next,cap; }e[maxn<<10]; void add(int u,int v,int c){ e[++size].to=v; e[size].next=h[u]; e[size].cap=c; h[u]=size; } int d[maxn]; queue<int> q; int bfs(){ memset(d,0,sizeof(d)); while(!q.empty()) q.pop(); d[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=h[u];i!=-1;i=e[i].next){ int v=e[i].to; if(!d[v]&&e[i].cap){ d[v]=d[u]+1; q.push(v); } } } return d[t]; } int dfs(int u,int lim){ if(u==t) return lim; int f=0,tmp; for(int i=h[u];i!=-1;i=e[i].next){ int v=e[i].to; if(d[v]==d[u]+1&&e[i].cap&&(tmp=dfs(v,min(lim,e[i].cap)))){ e[i].cap-=tmp,e[i^1].cap+=tmp; f+=tmp,lim-=tmp; if(!lim) return f; } } if(lim) d[u]=0; return f; } int dinic(){ int ans=0; while(bfs()){ ans+=dfs(s,INF); } return ans; } ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;} int main(){ T=read(),C=read(); while(T--){ memset(h,-1,sizeof(h)); n=read(),m=read(); s=0,t=n+m+1; for(int i=1;i<=m;i++) b[i]=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ a[i][j]=read(); v[i][a[i][j]].push_back(j); } } for(int i=1;i<=n;i++) S[i]=read(); for(int i=1;i<=m;i++){ add(i+n,t,b[i]),add(t,i+n,0); } for(int i=1;i<=n;i++){ int l=1,r=m; int res=m+1; while(l<=r){ int mid=(l+r)/2; memset(h,-1,sizeof(h)); size=1; for(int j=1;j<i;j++) add(s,j,1),add(j,s,0); for(int j=1;j<i;j++){ int now=res1[j]; for(int k=0;k<v[j][now].size();k++){ add(j,v[j][now][k]+n,1),add(v[j][now][k]+n,j,0); } } for(int j=1;j<=m;j++){ add(j+n,t,b[j]),add(t,j+n,0); } dinic(); add(s,i,1),add(i,s,0); for(int j=1;j<=mid;j++){ for(int k=0;k<v[i][j].size();k++){ add(i,v[i][j][k]+n,1),add(v[i][j][k]+n,i,1); } } if(dinic()){ res=mid; r=mid-1; }else{ l=mid+1; } } res1[i]=res; } for(int i=1;i<=n;i++) printf("%d ",res1[i]); printf("\n"); for(int i=1;i<=n;i++){ if(res1[i]>S[i]){ int l=1,r=i-1; int res=i; while(l<=r){ int mid=(l+r)/2; memset(h,-1,sizeof(h)); size=1; for(int j=1;j<i-mid;j++) add(s,j,1),add(j,s,0); for(int p=1;p<i-mid;p++){ int now=res1[p]; for(int k=0;k<v[p][now].size();k++){ add(p,v[p][now][k]+n,1),add(v[p][now][k]+n,p,0); } } for(int j=1;j<=m;j++){ add(j+n,t,b[j]),add(t,j+n,0); } dinic(); add(s,i,1),add(i,s,0); for(int j=1;j<=S[i];j++){ for(int k=0;k<v[i][j].size();k++){ add(i,v[i][j][k]+n,1),add(v[i][j][k]+n,i,0); } } if(dinic()){ res=mid; r=mid-1; }else{ l=mid+1; } } res2[i]=res; }else{ res2[i]=0; } } for(int i=1;i<=n;i++) printf("%d ",res2[i]); printf("\n"); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ v[i][j].clear(); } } } return 0; }