题解 P4382 【[八省联考2018]劈配】
liuzhangfeiabc · · 题解
蒟蒻强行发一波题解
据说这个题做法多种多样，花样跑匈牙利、dinic，甚至有人跑费用流都过了？
我写的是一种“变形匈牙利”，可能是sdoi全场跑得最快的之一。
大体思路就是，正常跑匈牙利时每个点只能匹配一个点，这里我们强行让每个导师的点可以匹配多个选手。
我们按照序号依次加入一个选手，对于每位选手枚举每个志愿的每个导师。
如果当前导师的名额还没用完，直接匹配成功。
否则，对这位导师已匹配的选手，再在同一志愿内寻找其他导师，能匹配则匹配成功。
这一部分与传统的匈牙利思路是类似的。
至于复杂度，每次加入一个人时，最多将所有人的某一志愿全部访问一遍，因此总复杂度是n ^ 2 * c的。
这样一来我们就可以解决第一问了，那么第二问呢？
我们第一个想法就是二分，因为答案显然具有可二分性。
对于每个答案k，先把前k-1个人跑一遍匈牙利，再加入当前这个人即可。
然而如果我们每次都需要重跑一遍匈牙利的话，复杂度就上升到了n ^ 3 c logn,对于0.3s一组数据来说会T。
不过我们可以暴力地记录每一个前缀跑匈牙利的结果，然后每次check时直接在对应版本上加入一个人即可。
总复杂度n ^ 2 c logn，luogu跑到92ms暂时应该是rk1。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
#define li long long
#define gc getchar()
#define pc putchar
#define kg pc(' ')
#define hh pc('\n')
li read(){
li x = 0,y = 1;
char c;
c = gc;
while(!isdigit(c)){
if(c == '-') y = -1;
c = gc;
}
while(isdigit(c)){
x = (x << 1) + (x << 3) + c - '0';
c = gc;
}
return x * y;
}
void print(li x){
if(x < 0){
pc('-');
x = -x;
}
if(x >= 10) print(x / 10);
pc(x % 10 + '0');
}
int t,c,n,m;
int a[210][210];
int zy[210][210][11],sl[210][210];
int mx[210],b[210];
bool vst[210];
int p1[210],p2[210][210],nw[210],an[210];
int tp1[210][210],tp2[210][210][210],tnw[210][210];
bool dfs(int q,int w){//匈牙利
int i,j,k,l;
for(j = 1;j <= sl[q][w];++j){
k = zy[q][w][j];
if(vst[k]) continue;
vst[k] = 1;
if(nw[k] < mx[k]){
p1[q] = k;
p2[k][++nw[k]] = q;
return 1;
}
for(l = 1;l <= mx[k];++l){
i = p2[k][l];
if(dfs(i,a[i][k])){
p1[q] = k;
p2[k][l] = q;
return 1;
}
}
}
return 0;
}
void wk1(){//第一问
int i,j,k;
for(i = 1;i <= n;++i){
memset(vst,0,sizeof(vst));
for(j = 1;j <= m;++j){
if(!sl[i][j]) continue;
if(dfs(i,j)) break;
}
//下面是复制匈牙利的结果
for(j = 1;j <= i;++j) tp1[i][j] = p1[j];
for(j = 1;j <= m;++j) tnw[i][j] = nw[j];
for(j = 1;j <= m;++j){
for(k = 1;k <= nw[j];++k) tp2[i][j][k] = p2[j][k];
}
}
}
bool wk2(int q,int w){//第二问的check，表示第q个人如果在第w名是否可行
int i,j;
for(i = 1;i <= w - 1;++i) p1[i] = tp1[w - 1][i];
for(i = 1;i <= m;++i) nw[i] = tnw[w - 1][i];
for(i = 1;i <= m;++i){
for(j = 1;j <= nw[i];++j) p2[i][j] = tp2[w - 1][i][j];
}//copy前w-1个人的结果
memset(vst,0,sizeof(vst));
for(i = 1;i <= b[q];++i){
if(!sl[q][i]) continue;
if(dfs(q,i)) return 1;
}
return 0;
}
int main(){
int i,j,l,r,mid,as;
t = read();
c = read();
while(t--){
memset(sl,0,sizeof(sl));
memset(p1,0,sizeof(p1));
memset(nw,0,sizeof(nw));
n = read();
m = read();
for(i = 1;i <= m;++i) mx[i] = read();
for(i = 1;i <= n;++i){
for(j = 1;j <= m;++j) {
a[i][j] = read();
if(a[i][j]) zy[i][a[i][j]][++sl[i][a[i][j]]] = j;
}
}
for(i = 1;i <= n;++i) a[i][0] = m + 1;
for(i = 1;i <= n;++i) b[i] = read();
wk1();
for(i = 1;i <= n;++i) {
an[i] = a[i][p1[i]];
print(an[i]);
kg;
}
hh;
for(i = 1;i <= n;++i){
if(an[i] <= b[i]){
putchar('0');kg;continue;
}
l = 1;r = i - 1;as = 0;
while(l <= r){
mid = l + r >> 1;
if(wk2(i,mid)) {
as = mid;
l = mid + 1;
}
else r = mid - 1;
}
print(i - as);kg;
}
hh;
}
return 0;
}update:
鉴于大多数人写的都是dinic，本蒟蒻再斗胆更新一波dinic算法的题解。
原点向每个选手连边，边权为1；每个导师向汇点连边，边权是这个导师的名额上限。
需要注意的一点是，这里的dinic需要动态加边。
同样还是枚举每个人，枚举每个志愿。
把这个人与这个志愿的导师连边，边权为1。
然后在残量网络上跑一次增广路，如果有流则匹配成功。
否则这一组的边就用不上了，不妨直接删除。（据说不这样的话会T?）
这样第1问就解决了。
对于第2问，同样可以二分答案并暴力记录每一个前缀的残量网络，然后直接加上前面所有组的边，跑一次增广路即可判断。
这样一来，由于二分图中dinic的复杂度大约为n * sqrt(n),所以总复杂度大约为n^2 sqrt(n) logn。
经过一番丧心病狂的底层优化后luogu跑到了180ms，也许是dinic的rk1？
#include<bits/stdc++.h>
using namespace std;
int p,c,n,m;
struct edge{
int fr,to,nxt,pre,val;
}e[10010],te[210][10010];
int tf[210][410],fir[410],dq[410],an[210],tct[210];
int cnt,s,g;
int q[100010],h,t;
int a[210][210],b[210],mx[210];
int sl[210][210],zy[210][210][11];
int vis[410];
#define gc getchar()
#define pc putchar
#define kg pc(' ')
#define hh pc('\n')
#define inf 987654321
#define rg register
inline int read(){
int x = 0;
char c;
c = gc;
while(!isdigit(c)) c = gc;
while(isdigit(c)){
x = (x << 1) + (x << 3) + c - '0';
c = gc;
}
return x;
}
void print(int x){
if(x >= 10) print(x / 10);
pc(x % 10 + '0');
}
inline void ins(int u,int v,int w){
e[++cnt].to = v;e[cnt].nxt = fir[u];e[cnt].fr = u;
if(fir[u]) e[fir[u]].pre = cnt;
fir[u] = cnt;e[cnt].val = w;
e[++cnt].to = u;e[cnt].nxt = fir[v];e[cnt].fr = v;
if(fir[v]) e[fir[v]].pre = cnt;
fir[v] = cnt;e[cnt].val = 0;
}
inline void in2(int u,int v,int w){//这里是底层优化
e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;e[cnt].val = w;
e[++cnt].to = u;e[cnt].nxt = fir[v];fir[v] = cnt;e[cnt].val = 0;
}
inline void del(int q){//删边，类似于从链表中删除元素的操作
if(e[q].nxt) e[e[q].nxt].pre = e[q].pre;
if(e[q].pre) e[e[q].pre].nxt = e[q].nxt;
if(q == fir[e[q].fr]) fir[e[q].fr] = e[q].nxt;
}
//以下是dinic
bool bfs(){
memset(vis,0,g * 4 + 4);
rg int i,j;
memcpy(dq,fir,g * 4 + 4);
h = t = 0;
q[++t] = s;
vis[s] = 1;
while(h < t){
j = q[++h];
for(i = fir[j];i;i = e[i].nxt){
if(e[i].val <= 0) continue;
if(vis[e[i].to]) continue;
vis[e[i].to] = vis[j] + 1;
q[++t] = e[i].to;
}
}
return vis[g];
}
int dfs(int q,int fl){
if(q == g) return fl;
int tp,nw = 0;
for(int &i = dq[q];i;i = e[i].nxt){
if(e[i].val <= 0) continue;
if(vis[e[i].to] != vis[q] + 1) continue;
tp = dfs(e[i].to,min(e[i].val,fl));
nw += tp;
e[i].val -= tp;
e[i ^ 1].val += tp;
if(nw == fl) return nw;
}
if(nw != fl) vis[q] = -1;
return nw;
}
void wk1(){//第一问
rg int i,j,k;
int l;
for(i = 1;i <= n;++i){
an[i] = m + 1;
ins(s,i,1);
for(j = 1;j <= m;++j){
if(!sl[i][j]) continue;
l = cnt;
for(k = 1;k <= sl[i][j];++k) ins(i,zy[i][j][k] + n,1);//动态加边
if(bfs() && dfs(s,inf)){
an[i] = j;
break;
}
else{
for(k = l;k <= cnt;++k) del(k);//动态删边
cnt = l;
}
}
//copy残量网络
for(j = 2;j <= cnt;++j) te[i][j] = e[j];
for(j = 1;j <= g;++j) tf[i][j] = fir[j];
tct[i] = cnt;
}
}
bool wk2(int q,int w){//第二问的check，表示第q个人如果在第w名是否可行
rg int i,j;
cnt = tct[w - 1];
for(i = 1;i <= g;++i) fir[i] = tf[w - 1][i];
for(i = 2;i <= cnt;++i) e[i] = te[w - 1][i];
//以上为copy前w-1个人的残量网络
ins(s,q,1);
for(i = 1;i <= b[q];++i){
if(!sl[q][i]) continue;
for(j = 1;j <= sl[q][i];++j) in2(q,zy[q][i][j] + n,1);
}
return bfs() && dfs(s,inf);
}
int main(){
rg int i,j;
int l,r,mid,as;
p = read();
c = read();
while(p--){
memset(sl,0,sizeof(sl));
memset(fir,0,sizeof(fir));
cnt = 1;
n = read();
m = read();
s = n + m + 1;
g = n + m + 2;
for(i = 1;i <= m;++i) {
mx[i] = read();
ins(i + n,g,mx[i]);
}
tct[0] = cnt;
for(i = 1;i <= g;++i) tf[0][i] = fir[i];
for(i = 2;i <= cnt;++i) te[0][i] = e[i];
//别忘了把一开始的边也记录下来，我在这里wa了若干次qwq
for(i = 1;i <= n;++i){
for(j = 1;j <= m;++j){
a[i][j] = read();
if(!a[i][j]) continue;
zy[i][a[i][j]][++sl[i][a[i][j]]] = j;
}
}
for(i = 1;i <= n;++i) b[i] = read();
wk1();
for(i = 1;i <= n;++i){
print(an[i]);
kg;
}
hh;
for(i = 1;i <= n;++i){
if(an[i] <= b[i]){
pc('0');kg;
continue;
}
l = 1;r = i - 1;as = 0;
while(l <= r){
mid = l + r >> 1;
if(wk2(i,mid)){
as = mid;
l = mid + 1;
}
else r = mid - 1;
}
print(i - as);kg;
}
hh;
}
return 0;
}