[八省联考2018] 劈配
一、题目
二、解法
自己一直想不出来，原来是陷入思维定式了。
你可以把选手和导师的关系看成是匹配（题目不也提示你了么），这时候 ( t dinic) 和匈牙利都是可以做的。
第 (i) 个选手可以按志愿等级来匹配，也就是先看能不能匹配到第 (1) 志愿的老师，然后第 (2) 志愿 (....) 我用的是 ( t dinic) ，所以可以每次把新的边建出来，然后在残量网络上跑最大流，如果最大流增加了那么就说明这个人匹配成功了。这样我们就解决了第一问。
第二问不难看出可以二分排名上升到第 (x) 位可以匹配到，第一问可以让我们得到前 (x-1) 人最优匹配后留下来的网络流图，然后再这张图上把所有志愿等级小于等于 (s_i) 的老师都连上，看能不能匹配。
我们要把前 (i) 个人最优匹配后的网络流图存下来，所以可以写一个结构体把图塞进去。思路其实并不难，但是一定要注意网络流不一定是建完图再跑，也可以便边建图边跑，这道题的实现有一定难度。
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int M = 405;
const int inf = 0x3f3f3f3f;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,m,k,s,t,p,tot,ans,f[M];vector<int> a[M][M];
struct edge
{
int v,c,next;
edge(int V=0,int C=0,int N=0) : v(V) , c(C) , next(N) {}
};
struct graph
{
int tot,ans,f[M],dis[M];edge e[12*M];
void init()
{
tot=1;ans=0;
for(int i=s;i<=t;i++) f[i]=0;
}
void add(int u,int v,int c)
{
e[++tot]=edge(v,c,f[u]),f[u]=tot;
e[++tot]=edge(u,0,f[v]),f[v]=tot;
}
int bfs()
{
queue<int> q;
for(int i=s;i<=t;i++) dis[i]=0;
q.push(s);dis[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
if(u==t) return 1;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(!dis[v] && e[i].c>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int ept)
{
if(u==t) return ept;
int flow=0,tmp=0;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+1 && e[i].c>0)
{
tmp=dfs(v,min(ept,e[i].c));
if(!tmp) continue;
e[i].c-=tmp;
e[i^1].c+=tmp;
flow+=tmp;
ept-=tmp;
if(!ept) break;
}
}
return flow;
}
void dinic()
{
while(bfs()) ans+=dfs(s,inf);
}
}g[M];
int check(int x)
{
g[n]=g[x-1];int tmp=g[x-1].ans;
for(int i=1;i<=k;i++)
for(int j=0;j<a[p][i].size();j++)
g[x-1].add(p,a[p][i][j]+n,1);
g[x-1].dinic();
int flag=g[x-1].ans>tmp;
g[x-1]=g[n];
return flag;
}
void dich(int l,int r)//二分上升到第几名
{
if(l>r) return ;
int mid=(l+r)>>1;
if(check(mid))
{
ans=mid;
dich(mid+1,r);
}
else dich(l,mid-1);
}
void work(int x)//找x的匹配
{
g[x]=g[x-1];//复制以前的图
tot=g[x].tot;//存档
for(int i=s;i<=t;i++) f[i]=g[x].f[i];
for(int i=1;i<=m;i++)
{
if(!a[x][i].size()) continue;//该档没有点
for(int j=0;j<a[x][i].size();j++)
{
int t=a[x][i][j];
g[x].add(x,t+n,1);
}
g[x].dinic();//残量网络上跑最大流
if(g[x].ans>g[x-1].ans)
{
printf("%d ",i);
return ;//成功匹配
}
g[x].tot=tot;//没有成功匹配要还原
for(int j=s;j<=t;j++) g[x].f[j]=f[j];
}
printf("%d ",m+1);
}
void solve()
{
n=read();m=read();
s=0;t=n+m+1;g[0].init();
for(int i=1;i<=m;i++)
g[0].add(i+n,t,read());
for(int i=1;i<=n;i++)
g[0].add(s,i,1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
a[i][j].clear();
for(int j=1;j<=m;j++)
{
int x=read();
if(x) a[i][x].push_back(j);
}
}
for(int i=1;i<=n;i++)
work(i);
puts("");
for(int i=1;i<=n;i++)
{
p=i;k=read();
ans=0;dich(1,i);
printf("%d ",i-ans);
}
puts("");
}
int main()
{
T=read();read();
while(T--) solve();
}