【2018八省联考】劈配

5251: [2018多省省队联测]劈配

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 89 Solved: 53
[Submit][Status][Discuss]

Description

一年一度的综艺节目《中国新代码》又开始了。

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当然轻松地解决了这个问题。

不过他还是想请你再算一遍，来检验自己计算的正确性。

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

Sample Output

2 1
1 0
1 2
0 1
1 3
0 1
三组数据分别与【题目描述】中的三个表格对应。
对于第1 组数据：由于选手1 没有填写第一志愿，所以他一定无法被第一志愿录取，也就一定会沮丧。
选手2 按原排名就不沮丧，因此他不需要提升排名。
对于第2 组和第3 组数据：1 号选手都不需要提升排名。
而希望被第一志愿录取的2 号选手都必须升到第1 名才能如愿。

这个题题目名称就十分诡异了。。。

考试的时候一看数据范围就知道两天里的那道网络流就是它了，然后开始思考网络流的做法，结果并没有YY出来。。。我还是太弱了。。。然后YY出了一个应该能过掉所有C=1的点的费用流做法。。。具体是什么就不说了，这题贪心就能有那么些分了。。。结果少memset一个数组华丽爆0.。。

回来mhr向我推荐了他的做法，就是对每一个人拆成志愿个数的点，然后动态加边跑网络流。我自己手动模拟了一下发现确实可以，于是胡乱打了一下，结果，4000+的网络流。。。交上去发现70，最后三个c==10的点没过。仔细思考之后发现找到的每个人被第几志愿录取没有问题，主要在第二问上出错了。然后思考如何更精准的找到，发现二分可行，但是mhr这方法的二分严重超时无法使用。。。于是开始YY能不能不拆点。。结果发现可行。就是直接每次暴力重新建图，利用已经得出的结果建造最优的图，然后暴力DINIC。结果并不慢。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define inf 50000001
#define ll long long
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
struct po{
    int nxt,to,w;
};
po edge[6000001];
int T,C,n,m,s,t;
int head[501],dep[501],num=-1,b[205],want[202];
int a[205][205],rs[205][205],ql[202],ans,cur[501],last,tag;
int out1[201],out2[201];
inline int read()
{
    int x=0,c=1;
    char ch=' ';
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    while(ch=='-')c*=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
    return x*c;
}
inline void add_edge(int from,int to,int w)
{
    edge[++num].nxt=head[from];
    edge[num].to=to;
    edge[num].w=w;
    head[from]=num;
}
inline void add(int from,int to,int w)
{
    add_edge(from,to,w);
    add_edge(to,from,0);
}
inline bool bfs()
{
    memset(dep,0,sizeof(dep));
    queue<int> q;
    while(!q.empty())
    q.pop();
    q.push(s);
    dep[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(re int i=head[u];i!=-1;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if(dep[v]==0&&edge[i].w>0)
            {
                dep[v]=dep[u]+1;
                if(v==t)
                return 1;
                q.push(v);
            }
        }
    }
    return 0;
}
inline int dfs(int u,int dis)
{
    if(u==t) return dis;
    int diss=0;
    for(re int& i=cur[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].to;
        if(edge[i].w!=0&&dep[v]==dep[u]+1){
            int check=dfs(v,min(dis,edge[i].w));
            if(check>0)
            {
                dis-=check;
                diss+=check;
                edge[i].w-=check;
                edge[i^1].w+=check;
                if(dis==0) break;
            }
        }
    }
    return diss;
}
inline void dinic()
{
    while(bfs())
    {
        for(re int i=s;i<=t;i++)
            cur[i]=head[i];
        while(int d=dfs(s,inf)) ans+=d;
    }
}
void init(){
    memset(out1,0,sizeof(out1));
    memset(out2,0,sizeof(out2));
    n=read();m=read();
    s=0;t=m+n+1;
    for(re int i=1;i<=n;i++) out1[i]=m+1;
    for(re int i=1;i<=m;i++) b[i]=read();
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++)
            a[i][j]=read();        
    for(re int i=1;i<=n;i++) want[i]=read();
}
int main()
{
    //freopen("date.in","r",stdin);
    T=read();C=read();
    while(T--){
        init();
        for(re int i=1;i<=n;i++){
            num=-1;memset(head,-1,sizeof(head));
            for(re int j=1;j<=n;j++){if(j==i) tag=num+1;add(s,j,1);}
            for(re int j=1;j<=m;j++) add(n+j,t,b[j]);
            for(re int j=1;j<i;j++)
                for(re int l=1;l<=m;l++)
                    if(a[j][l]==out1[j]) add(j,n+l,1);
            dinic();
            for(re int l=1;l<=m;l++){
                for(re int j=1;j<=m;j++)
                    if(a[i][j]==l) add(i,n+j,1);
                dinic();
                if(edge[tag].w==0){out1[i]=l;break;}
            }
        }
        for(re int i=1;i<=n;i++){
            if(out1[i]<=want[i]) continue;
            int l=1,r=i-1;out2[i]=i;
            while(l<=r){
                num=-1;memset(head,-1,sizeof(head));
                for(re int j=1;j<=n;j++){if(j==i) tag=num+1;add(s,j,1);}
                for(re int j=1;j<=m;j++) add(n+j,t,b[j]);
                int mid=l+r>>1;
                for(re int j=1;j<mid;j++)
                    for(re int l=1;l<=m;l++)
                        if(a[j][l]==out1[j]) add(j,n+l,1);
                dinic();
                for(re int j=1;j<=m;j++)
                    if(a[i][j]>0&&a[i][j]<=want[i]) add(i,n+j,1);
                dinic();
                if(edge[tag].w==0) {l=mid+1;out2[i]=i-mid;}
                else r=mid-1;
            }
        }
        for(re int i=1;i<=n;i++)
        cout<<out1[i]<<" ";
        cout<<endl;
        for(re int i=1;i<=n;i++)
        cout<<out2[i]<<" ";
        cout<<endl;    
    }
}