自动搬运

查看原文

来自洛谷，原作者为

	liuzhangfeiabc **

搬运于2025-08-24 21:59:35，当前版本为作者最后更新于2018-04-08 11:57:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻强行发一波题解

据说这个题做法多种多样，花样跑匈牙利、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;
}