Input
每个测试点包含多组测试数据
第一行2个用空格隔开的非负整数T;C,分别表示数据组数、每档志愿最多允许填写的导师数目。
接下来依次描述每组数据,对于每组数据:
第1行两个用空格隔开的正整数n;m。
n;m分别表示选手的数量、导师的数量。
第2行m个用空格隔开的正整数:其中第i个整数为bi。
Bi表示编号为i的导师战队人数的上限。
第3行至第n+2行,每行m个用空格隔开的非负整数:其中第i+2行左起第j个数为ai,j
ai,j表示编号为i的选手将编号为j的导师编排在了第ai,j志愿。特别地,如果ai,j=0,则表示该选手没有将该导师填入志愿表。
在这一部分,保证每行中不存在某一个正数出现超过C次(0可能出现超过C次),同时保证所有ai,j<=m。
第n+3行n个用空格隔开的正整数,其中第i个整数为Si
Si表示编号为i的选手的理想值。
在这一部分,保证Si<=m。
T<=5,m<=n<=200,Bi<=N
Output
按顺序输出每组数据的答案。对于每组数据,输出2行:
第1行输出n个用空格隔开的正整数,其中第i个整数的意义为:
在最优的录取方案中,编号为i的选手会被该档志愿录取。
特别地,如果该选手出局,则这个数为m+1。
第2行输出n个用空格隔开的非负整数,其中第i个整数的意义为:
使编号为i的选手不沮丧,最少需要让他上升的排名数。
特别地,如果该选手一定会沮丧,则这个数为i。
Sample Input
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
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
Sample Output
2 1
1 0
1 2
0 1
1 3
0 1
三组数据分别与【题目描述】中的三个表格对应。
对于第1 组数据:由于选手1 没有填写第一志愿,所以他一定无法被第一志愿录取,也就一定会沮丧。
选手2 按原排名就不沮丧,因此他不需要提升排名。
对于第2 组和第3 组数据:1 号选手都不需要提升排名。
而希望被第一志愿录取 的2 号选手都必须升到第1 名才能如愿。
[Submit][Status][Discuss]
1、2440 6.0BSP移植过程之camera驱动移植
2、VB.net版本的数据库访问类DataBaseAccess
3、Jmeter(二)乱码问题
4、springBoot集成redisCluster
5、【11】淘宝sdk的DOM、CSS规范、Widget规范(这个Widget规范差不多就是网页效果)和HTML规范
1 0
1 2
0 1
1 3
0 1
三组数据分别与【题目描述】中的三个表格对应。
对于第1 组数据:由于选手1 没有填写第一志愿,所以他一定无法被第一志愿录取,也就一定会沮丧。
选手2 按原排名就不沮丧,因此他不需要提升排名。
对于第2 组和第3 组数据:1 号选手都不需要提升排名。
而希望被第一志愿录取 的2 号选手都必须升到第1 名才能如愿。
HINT
原题面:www.lydsy.com/JudgeOnline/upload/201804/day2(3).pdf
Source
D2唯一有区分度的题。。正解好像有4种,下面说一个Dinic做法。
首先如果你非常巧妙地避开了所有有关二分图和网络流的思路,你也可以通过各种数据分治拿到70分,但是码量感觉不可想象。
先之考虑第一问,第二问实在不行二分答案或者暴力枚举跑m次第一问就好。
看原题面可以看到b[i]=1的50分,这启发我们想到二分图,因为每个选手对应一位导师,而匈牙利算法正好保证了每次增广都保证前面的选手都能匹配上。那么b[i]>1的怎么处理呢?不就是网络流嘛,直接将导师的点向汇点连容量为b[i]的边就好了。
考虑具体做法,对于当前考虑的选手,每次向一组导师全部连边,如果增广成功则考虑下一个选手。
怎么证明是对的呢?首先我们知道网络流每次能够增广当且仅当流量能变大,所以在增广这个点的同时不可能让前面所有的选手找不到匹配,所以我们一边加边一边跑Dinic即可。
至于第二问,第一反应肯定是二分答案然后暴力重建图,这样好像是可以过的,但是我们可以先连上所有这个点的边,然后从第一名开始增广,知道找不到增广则停止,这样复杂度就和上面第一问同阶了。$O(f(n,n^2)n)$,其中$f(n,m)$表示n个点m条边的二分图匹配的复杂度,也就是$O(nm)$,实际上跑不满。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 #define rep(i,l,r) for (int i=l; i<=r; i++) 6 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 7 using namespace std; 8 9 const int N=410,M=80100,inf=1000000000; 10 int n,m,k,cas,ans,cnt,S,T,b[N],dis[N],h[N],q[M],nxt[M],to[M],f[M],res[N]; 11 vector<int>V[N][N]; 12 13 void add(int u,int v,int w){ 14 to[++cnt]=v; f[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; 15 to[++cnt]=u; f[cnt]=0; nxt[cnt]=h[v]; h[v]=cnt; 16 } 17 18 void init(){ 19 cnt=1; S=n+m+1; T=n+m+2; 20 memset(h,0,sizeof(h)); 21 rep(i,1,n) add(S,i,1); 22 rep(i,1,m) add(i+n,T,b[i]); 23 } 24 25 bool bfs(){ 26 rep(i,0,T) dis[i]=0; 27 dis[S]=1; q[1]=S; 28 for (int st=0,ed=1; st!=ed; ){ 29 int x=q[++st]; 30 For(i,x) if (!dis[k=to[i]] && f[i]) 31 dis[k]=dis[x]+1,q[++ed]=k; 32 } 33 return dis[T]; 34 } 35 36 int dfs(int x,int lim){ 37 if (x==T) return lim; 38 int c=0; 39 For(i,x) if (dis[k=to[i]]==dis[x]+1 && f[i]){ 40 int t=dfs(k,min(lim-c,f[i])); 41 f[i]-=t; f[i^1]+=t; c+=t; 42 if (c==lim) return lim; 43 } 44 if (!c) dis[x]=-1; 45 return c; 46 } 47 48 bool work(int x,int l,int r){ 49 rep(i,l,r) rep(j,0,(int)V[x][i].size()-1) add(x,V[x][i][j]+n,1); 50 if (bfs()) { dfs(S,inf); return 1; } 51 return 0; 52 } 53 54 int main(){ 55 for (scanf("%d%*d",&cas); cas--; ){ 56 scanf("%d%d",&n,&m); 57 rep(i,1,m) scanf("%d",&b[i]); 58 rep(i,1,n) rep(j,1,m) V[i][j].clear(); 59 rep(i,1,n) rep(j,1,m) scanf("%d",&k),V[i][k].push_back(j); 60 init(); 61 rep(i,1,n){ 62 for (res[i]=1; res[i]<=m; res[i]++) if (work(i,res[i],res[i])) break; 63 printf("%d ",res[i]); 64 } 65 puts(""); 66 rep(i,1,n){ 67 scanf("%d",&k); ans=i; init(); 68 if (!work(i,1,k)) { printf("%d ",i); continue; } 69 for (int j=1; --ans; j++){ 70 if (res[j]>m) continue; 71 if (!work(j,res[j],res[j])) break; 72 } 73 printf("%d ",ans); 74 } 75 puts(""); 76 } 77 return 0; 78 }优质内容筛选与推荐>>
1、2440 6.0BSP移植过程之camera驱动移植
2、VB.net版本的数据库访问类DataBaseAccess
3、Jmeter(二)乱码问题
4、springBoot集成redisCluster
5、【11】淘宝sdk的DOM、CSS规范、Widget规范(这个Widget规范差不多就是网页效果)和HTML规范