https://www.lydsy.com/JudgeOnline/problem.php?id=5251
https://loj.ac/problem/2477 <-可以看数据
https://www.luogu.org/problemnew/show/P4382
题面太长，请自行读完之后再看本题。
考试的时候让我伤心的一道题，分明想的就是正解结果sb般第二问没二分丢了15分。
如果b=1就是一个显然的匈牙利匹配了。
考虑b!=1也只不过就是让一个导师可以多匹配几个人而已，额外记录这个导师是否还能匹配人即可。
那么对于第一问显而易见匈牙利算法即可完成，复杂度最差就是每个人的其中一个志愿被我们遍历一遍，于是一次匈牙利是O(n*c)，总共O(n^2*c)。
第二问二分答案后对这个点再匈牙利一次，实际就是清出答案和现在这个点之间的点的所有答案，而且我们已经知道了它之前的所有人的志愿和导师选择，因此大可以直接复制下来而不用重新跑一遍。
因此是O(n^2*logn*c)轻松跑过。
（至于为什么debug这么久纯粹是因为我傻，没有考虑匈牙利算法可以增广的不只有它前面的点，还可以有后面的点。）
总结：一道好题，洛谷评分虚高，实际为省选/NOI-，但是为了纪念我debug的时间之长，于是评了个NOI。
#include<cmath> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<iostream> using namespace std; const int N=210; inline int read(){ int X=0,w=1;char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9')X=(X<<1)+(X<<3)+ch-'0',ch=getchar(); return X*w; } int n,m,b[N],bb[N],s[N]; int ds[N],zy[N],dds[N],zzy[N]; int a[N][N][11],len[N][N]; bool vis[N]; bool dfs(int k,int w){ for(int j=1;j<=len[k][w];j++){ int u=a[k][w][j]; if(vis[u])continue; vis[u]=1; if(b[u]){ ds[k]=u;zy[k]=w; b[u]--; return 1; }else{ for(int l=1;l<=n;l++){//这里debug 3h+才发现。 if(l==k)continue; if(ds[l]==u){ if(dfs(l,zy[l])){ ds[k]=u;zy[k]=w; return 1; } } } } } return 0; } inline void copy(int k){ for(int i=1;i<=m;i++)b[i]=bb[i]; for(int i=1;i<=k;i++){ ds[i]=dds[i]; zy[i]=zzy[i]; b[ds[i]]--; } for(int i=k+1;i<=n;i++)ds[i]=-1; return; } inline void work2(){ for(int i=1;i<=n;i++){ if(zzy[i]<=s[i])printf("0 "); else{ int l=1,r=i-1,ans=0; while(l<=r){ int mid=(l+r)>>1; bool ok=0; copy(mid-1); memset(vis,0,sizeof(vis)); for(int j=1;j<=s[i];j++){ if(dfs(i,j)){ ans=mid;l=mid+1; ok=1; break; } } if(!ok)r=mid-1; } printf("%d ",i-ans); } } puts(""); } inline void work1(){ for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); for(int j=1;j<=m;j++){ if(!len[i][j])continue; if(dfs(i,j))break; } } for(int i=1;i<=n;i++){ zzy[i]=zy[i];dds[i]=ds[i]; printf("%d ",zy[i]); } puts(""); } inline void init(){ n=read(),m=read(); memset(len,0,sizeof(len)); for(int i=1;i<=m;i++)bb[i]=b[i]=read(); for(int i=1;i<=n;i++){ zy[i]=m+1;ds[i]=-1; for(int j=1;j<=m;j++){ int k=read(); if(k)a[i][k][++len[i][k]]=j; } } for(int i=1;i<=n;i++)s[i]=read(); } int main(){ int t=read(),c=read(); while(t--){ init(); work1(); work2(); } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++