题意：
有n位选手和m位导师，每位导师战队有容量限制 bi b i 。
每位选手有一张志愿表。对于每位选手，导师之间允许并列（最多允许C位导师并列）。所有选手有一个排名，选手之间不允许并列。
导师录取的规则可以简单概括为：对每位选手，在优先满足更高位选手的前提下，尽可能满足该选手最高位志愿。
每位选手有一个理想的志愿s_i（梦想），表示他希望被s_i或更高位的志愿录取。
求：
1.每位选手的最终录取情况。
2.每位选手至少要上升几名，才能被理想的志愿录取（实现梦想）。
n,m≤200 C≤10 n , m ≤ 200 C ≤ 10
Solution：
考场上只想到了费用流，但是T掉了，自测是跑了3s，在此分享一下费用流做法：
因为我们每次需要优先满足排名在前的选手，志愿在前的导师，所以说我们S向每个选手连费用为1000*排名，流量为1的边，每个导师向T连费用为0，流量为人数上限的边，每个选手向导师连费用为志愿优先级，流量为1的边，这样对于每次跑出的费用V, V1000 V 1000 是这个选手的排名， V%1000 V % 1000 是这个选手能满足的最高志愿。
但是这样直接跑是错的（过不了大样例），我们需要每次重新建图，对于每个已知结果的选手，我们连边的时候只能连和结果志愿一样的边，理由大概就是后面的流在跑的时候可能会通过前面建的回流来影响前面的结果
这样我们需要枚举每个选手，然后每次重新建图+费用流
至于第二问只需要二分一下就好了
复杂度大概是 O(n∗n∗n∗c) O ( n ∗ n ∗ n ∗ c ) （费用流复杂度大概是 n∗n∗c n ∗ n ∗ c ）
代码（TLE）：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=410;
const int inf=1e9;
int n,m,t,C,S,T,sz,head[N],ans[N],a[300][300],b[300],dis[N],q[N*N],s[N];
bool vis[N];
int pre[N],prv[N];
struct edg{
int to,next,v,f;
}e[200*N];
void add(int x,int y,int f,int v)
{
sz++;e[sz].to=y;e[sz].f=f;e[sz].v=v;e[sz].next=head[x];head[x]=sz;
sz++;e[sz].to=x;e[sz].f=0;e[sz].v=-v;e[sz].next=head[y];head[y]=sz;
}
bool SPFA()
{
int tt=0,hh=0;
for (int i=S;i<=T;++i) vis[i]=0,dis[i]=inf;
vis[S]=1;dis[S]=0;q[++tt]=S;
while (hh<tt)
{
int x=q[++hh];vis[x]=0;
for (int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (e[i].f&&dis[y]>dis[x]+e[i].v)
{
dis[y]=dis[x]+e[i].v;
pre[y]=i;prv[y]=x;
if (!vis[y]) q[++tt]=y,vis[y]=1;
}
}
}
return (dis[T]!=inf);
}
int main()
{
freopen("mentor.in","r",stdin);
freopen("mentor.out","w",stdout);
scanf("%d%d",&t,&C);
while (t--)
{
sz=1;memset(head,0,sizeof(head));
scanf("%d%d",&n,&m);S=0;T=n+m+1;
for (int i=1;i<=n;++i) ans[i]=m+1;
for (int i=1;i<=m;++i) scanf("%d",&b[i]);
for (int i=1;i<=n;++i)
{
sz=1;memset(head,0,sizeof(head));
for (int j=1;j<=n;++j) add(S,j,1,j*1000);
for (int j=1;j<=m;++j) add(n+j,T,b[j],0);
for (int j=1;j<i;++j)
for (int k=1;k<=m;++k)
if (a[j][k]==ans[j]) add(j,n+k,1,a[j][k]);
for (int j=1;j<=m;++j)
{
scanf("%d",&a[i][j]);
if (a[i][j]) add(i,n+j,1,a[i][j]);
}
while (SPFA())
{
ans[dis[T]/1000]=dis[T]%1000;
for (int i=T;i!=S;i=prv[i])
e[pre[i]].f--,e[pre[i]^1].f++;
}
}
for (int x,i=1;i<=n;++i)
{
scanf("%d",&x);s[i]=0;
if (x>=ans[i]) continue;
int l=1,r=i-1;s[i]=i;
while (l<=r)
{
sz=1;memset(head,0,sizeof(head));
for (int j=1;j<=n;++j) add(S,j,1,j*1000);
for (int j=1;j<=m;++j) add(n+j,T,b[j],0);
int mid=l+r>>1;
for (int j=1;j<mid;++j)
for (int k=1;k<=m;++k)
if (a[j][k]==ans[j]) add(j,n+k,1,a[j][k]);
for (int j=1;j<=m;++j)
if (a[i][j]) add(i,n+j,1,a[i][j]);
bool p=0;
while (SPFA())
{
if (dis[T]/1000==i)
{
p=1;
if (dis[T]%1000<=x) {
s[i]=i-mid;l=mid+1;break;}
else {r=mid-1;break;}
}
//cout<<dis[T]<<endl;
for (int i=T;i!=S;i=prv[i])
e[pre[i]].f--,e[pre[i]^1].f++;
}
if (!p) r=mid-1;
}
}
for (int i=1;i<=n;++i)
printf("%d ",ans[i]);
printf("\n");
for (int i=1;i<=n;++i)
printf("%d ",s[i]);
printf("\n");
}
}普通网络流思路和费用流差不多，只需要对于每个选手枚举一个志愿即可了，对于每个选手只需要重新建边一次，枚举志愿时可以直接加边
第二问也是二分
复杂度 O(n∗m∗nc−−√) O ( n ∗ m ∗ n c ) ( nc−−√ n c 是二分图dinic复杂度)
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=410;
const int inf=1e9;
int n,m,t,C,S,T,sz,head[N],v[N],ans[N],a[300][300],b[300],dis[N],q[N],s[N];
int dep[N];
int pre[N],prv[N];
struct edg{
int to,next,f;
}e[200*N];
void add(int x,int y,int f)
{
sz++;e[sz].to=y;e[sz].f=f;e[sz].next=head[x];head[x]=sz;
sz++;e[sz].to=x;e[sz].f=0;e[sz].next=head[y];head[y]=sz;
}
bool bfs()
{
int hh=0,tt=0;
for (int i=S;i<=T;i++) dep[i]=0;
dep[S]=1;q[++tt]=S;
while (hh<tt)
{
int x=q[++hh];
for (int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (e[i].f&&!dep[y]) dep[y]=dep[x]+1,q[++tt]=y;
}
}
return (dep[T]!=0);
}
int dfs(int x,int flow)
{
if (x==T) return flow;
int used=0,now=0;
for (int i=v[x];i;i=e[i].next)
{
int y=e[i].to;
if (dep[y]==dep[x]+1&&e[i].f)
{
now=dfs(y,min(flow-used,e[i].f));
e[i].f-=now;
e[i^1].f+=now;
used+=now;
v[x]=i;
if (flow==used) break;
}
}
if (used==0) dep[x]=-1;
return used;
}
int main()
{
// freopen("mentor.in","r",stdin);
// freopen("mentor.out","w",stdout);
scanf("%d%d",&t,&C);
while (t--)
{
sz=1;memset(head,0,sizeof(head));
scanf("%d%d",&n,&m);S=0;T=n+m+1;
for (int i=1;i<=n;++i) ans[i]=m+1;
for (int i=1;i<=m;++i) scanf("%d",&b[i]);
int tag=0;
for (int i=1;i<=n;++i)
{
sz=1;memset(head,0,sizeof(head));
for (int j=1;j<=i;++j) {
if (j==i) tag=sz+1;add(S,j,1);}
for (int j=1;j<=m;++j) add(n+j,T,b[j]);
for (int j=1;j<i;++j)
for (int k=1;k<=m;++k)
if (a[j][k]==ans[j]) add(j,n+k,1);
for (int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
while (bfs())
{
for (int j=S;j<=T;++j) v[j]=head[j];
dfs(S,inf);
}
for (int l=1;l<=m;++l)
{
for (int j=1;j<=m;++j)
if (a[i][j]==l) add(i,n+j,1);
while (bfs())
{
for (int j=S;j<=T;++j) v[j]=head[j];
dfs(S,inf);
}
if (e[tag].f==0) {ans[i]=l;break;}
}
}
for (int x,i=1;i<=n;++i)
{
scanf("%d",&x);s[i]=0;
if (x>=ans[i]) continue;
int l=1,r=i-1;s[i]=i;
while (l<=r)
{
sz=1;memset(head,0,sizeof(head));
for (int j=1;j<=n;++j) {
if (j==i) tag=sz+1;add(S,j,1);}
for (int j=1;j<=m;++j) add(n+j,T,b[j]);
int mid=l+r>>1;
for (int j=1;j<mid;++j)
for (int k=1;k<=m;++k)
if (a[j][k]==ans[j]) add(j,n+k,1);
while (bfs())
{
for (int j=S;j<=T;++j) v[j]=head[j];
dfs(S,inf);
}
for (int j=1;j<=m;++j)
if (a[i][j]>0&&a[i][j]<=x) add(i,n+j,1);
while (bfs())
{
for (int j=S;j<=T;++j) v[j]=head[j];
dfs(S,inf);
}
if (e[tag].f==0) {l=mid+1,s[i]=i-mid;}
else r=mid-1;
}
}
for (int i=1;i<=n;++i)
printf("%d ",ans[i]);
printf("\n");
for (int i=1;i<=n;++i)
printf("%d ",s[i]);
printf("\n");
}
}
京公网安备 11010502036488号