洛谷4382 [八省联考2018]劈配

加边的同时增广

阅读全文大概需要 3分钟
本文总阅读量
Posted by yjjr's blog on April 12, 2018

标签:网络流

题目

题目传送门

题目背景

一年一度的综艺节目《中国新代码》又开始了。Zayid 从小就梦想成为一名程序员,他觉得这是一个展示自己的舞台,于是他毫不犹豫地报名了。

题目描述

轻车熟路的Zayid 顺利地通过了海选,接下来的环节是导师盲选,这一阶段的规则是这样的:

总共n 名参赛选手(编号从1 至n)每人写出一份代码并介绍自己的梦想。接着 由所有导师对这些选手进行排名。为了避免后续的麻烦,规定不存在排名并列的情况。

同时,每名选手都将独立地填写一份志愿表,来对总共 m 位导师(编号从 1 至 m)作出评价。志愿表上包含了共m 档志愿。对于每一档志愿,选手被允许填写最多C 位导师,每位导师最多被每位选手填写一次(放弃某些导师也是被允许的)。

在双方的工作都完成后,进行录取工作。每位导师都有自己战队的人数上限,这意味着可能有部分选手的较高志愿、甚至是全部志愿无法得到满足。节目组对”前i 名的录取结果最优“ 作出如下定义:

  • 前1 名的录取结果最优,当且仅当第1 名被其最高非空志愿录取(特别地,如 果第1 名没有填写志愿表,那么该选手出局)。

  • 前i 名的录取结果最优,当且仅当在前i - 1 名的录取结果最优的情况下:第i 名 被其理论可能的最高志愿录取(特别地,如果第i 名没有填写志愿表、或其所有 志愿中的导师战队均已满员,那么该选手出局)。

如果一种方案满足‘‘前n 名的录取结果最优’’,那么我们可以简称这种方案是最 优的。

举例而言,2 位导师T 老师、F 老师的战队人数上限分别都是1 人;2 位选手 Zayid、DuckD 分列第1、2 名。那么下面3 种志愿表及其对应的最优录取结果如表中所示:

可以证明,对于上面的志愿表,对应的方案都是唯一的最优录取结果。

每个人都有一个自己的理想值si,表示第i 位同学希望自己被第si 或更高的志愿录取,如果没有,那么他就会非常沮丧。

现在,所有选手的志愿表和排名都已公示。巧合的是,每位选手的排名都恰好与它们的编号相同。

对于每一位选手,Zayid 都想知道下面两个问题的答案:

  • 在最优的录取方案中,他会被第几志愿录取。

  • 在其他选手相对排名不变的情况下,至少上升多少名才能使得他不沮丧。

作为《中国新代码》的实力派代码手,Zayid 当然轻松地解决了这个问题。不过他还是想请你再算一遍,来检验自己计算的正确性。

输入输出格式

输入格式

从文件mentor.in 中读入数据。

每个测试点包含多组测试数据,第一行 2 个用空格隔开的非负整数 T;C,分别表示数据组数、每档志愿最多允许填写的导师数目。

接下来依次描述每组数据,对于每组数据:

  • 第1 行两个用空格隔开的正整数n;m。

    n;m 分别表示选手的数量、导师的数量。

  • 第2 行m 个用空格隔开的正整数:其中第i 个整数为\(b_i\)。

    \(b_i\) 表示编号为i 的导师战队人数的上限。

  • 第3 行至第n + 2 行,每行m 个用空格隔开的非负整数:其中第i + 2 行左起第 j 个数为\(a_{i,j}\)。

    \(a_{i,j}\) 表示编号为i 的选手将编号为j 的导师编排在了第\(a_{i,j}\) 志愿。特别地,如果\(a_{i,j}\) = 0,则表示该选手没有将该导师填入志愿表。

    在这一部分,保证每行中不存在某一个正数出现超过 C 次(0 可能出现超 过C 次),同时保证所有\(a_{i,j}\) <= m。

  • 第n + 3 行n 个用空格隔开的正整数,其中第i 个整数为\(s_i\)。

    \(s_i\) 表示编号为i 的选手的理想值。

    在这一部分,保证\(s_i\) <= m。

输出格式

输出到文件mentor.out 中。

按顺序输出每组数据的答案。对于每组数据,输出2 行:

  • 第1 行输出n 个用空格隔开的正整数,其中第i 个整数的意义为:

在最优的录取方案中,编号为i 的选手会被该档志愿录取。

特别地,如果该选手出局,则这个数为m + 1。

  • 第 2 行输出 n 个用空格隔开的非负整数,其中第 i 个整数的意义为:

使编号为i 的选手不沮丧,最少需要让他上升的排名数。

特别地,如果该选手一定会沮丧,则这个数为i。

输入输出样例

输入样例#1

3 5
2 2
1 1
2 2
1 2
1 1
2 2
1 1
1 2
1 2
2 1
2 2
1 1
0 1
0 1
2 2

输出样例#1

2 1
1 0
1 2
0 1
1 3
0 1

输入样例#2

1 5
4 3
2 1 1
3 1 3
0 0 1
3 1 2
2 3 1
2 3 3 3

###输出样例#2

1 1 3 2
0 0 0 0

说明

【样例1 解释】

三组数据分别与【题目描述】中的三个表格对应。

对于第1 组数据:由于选手1 没有填写第一志愿,所以他一定无法被第一志愿录 取,也就一定会沮丧。选手2 按原排名就不沮丧,因此他不需要提升排名。

对于第2 组和第3 组数据:1 号选手都不需要提升排名。而希望被第一志愿录取 的2 号选手都必须升到第1 名才能如愿。

【样例2 解释】

1 号选手的第一志愿只填写了2 号导师,因此1 号选手必定被2 号导师录取。

2 号选手的第一志愿只填写了3 号导师,因此2 号选手必定被3 号导师录取。

由于2; 3 号导师均满员,且3; 4 号选手均填写了1 号导师,因此它们都会被1 号 导师录取。

所以1; 2 号选手均被第1 志愿录取,3 号选手被第3 志愿录取,4 号选手被第2 志 愿录取。

由于他们都如愿以偿了,所以他们都不需要提升名次。

分析

将导师的点向汇点T连容量为b[i]的边

考虑当前的选手,每次向一组导师全部连边,如果增广成功则考虑下一位选手

加边的同时增广跑dinic

第二问可以先连上所有这个点的边,然后从第一名开始增广,直到找不到增广则停止

O(能过)

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define pb push_back
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=506,maxm=8e4+6,inf=1e9;
int n,m,k,ans,T,TT,S,c,cnt,last[maxn],b[maxn],dis[maxn],h[maxn],que[maxm],res[maxn];
struct edge{int to,next,v;}e[maxm<<1];
vector<int> V[maxn][maxn];
void insert(int u,int v,int w){
	e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
	e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}
void init(){
	cnt=1;S=n+m+1;T=S+1;mem(last,0);
	rep(i,1,n)insert(S,i,1);
	rep(i,1,m)insert(i+n,T,b[i]);
}
inline bool bfs(){
	int head=0,tail=1,now;
	mem(h,-1);que[0]=S;h[S]=0;
	while(head<tail){
		now=que[head++];
		reg(now)
			if(e[i].v&&h[e[i].to]==-1){h[e[i].to]=h[now]+1;que[tail++]=e[i].to;}
	}
	return h[T]!=-1;
}
inline int dfs(int x,int f){
	if(x==T)return f;
	int w,used=0;
	reg(x)
		if(e[i].v&&h[e[i].to]==h[x]+1){
			w=dfs(e[i].to,min(f-used,e[i].v));
			e[i].v-=w;e[i^1].v+=w;
			used+=w;if(used==f)return f;
		}
	if(!used)h[x]=-1;
	return used;
}
inline bool work(int x,int l,int r){
	rep(i,l,r)rep(j,0,(int)V[x][i].size()-1)insert(x,V[x][i][j]+n,1);
	if(bfs()){dfs(S,inf);return 1;}return 0;
}
int main(){
	TT=read(),c=read();
	while(TT--){
		n=read(),m=read();
		rep(i,1,m)b[i]=read();
		rep(i,1,n)rep(j,1,m)V[i][j].clear();
		rep(i,1,n)rep(j,1,m)k=read(),V[i][k].pb(j);
		init();
		rep(i,1,n){
			for(res[i]=1;res[i]<=m;res[i]++)if(work(i,res[i],res[i]))break;
			printf("%d ",res[i]);
		}
		puts("");
		rep(i,1,n){
			k=read();ans=i;init();
			if(!work(i,1,k)){printf("%d ",i);continue;}
			for(int j=1;--ans;j++){
				if(res[j]>m)continue;
				if(!work(j,res[j],res[j]))break;
			}
			printf("%d ",ans);
		}
		puts("");
	}
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr