题解 P4382 【[八省联考2018]劈配】

· · 题解

一种时空复杂度均严格与 C 无关的做法。

首先，看到这个问题，一下子就能想到二分图多重匹配的模型——每个选手均可以匹配多个导师，而导师有着匹配人数的上限。

于是我们从小到大枚举每个人，再枚举其所有档志愿，依次判断其该档志愿的边加入图中会不会使最大流量变大即可。

为了避免一些奇奇怪怪的错误，我的写法是加入一档志愿后，若合法，则不退流，直接进行下一个人的运算；否则，就要退流，消除本档志愿的影响。具体而言，因为我们的建图是从 S 连到所有人，从所有人连到合法的导师，从所有导师再连到 T；于是当想要仅对一个人退流时，就断掉其与 S 的连边，并且以 T 为源点，此人所对应的节点为汇点，跑一遍Dinic，然后再连回该连边即可。为了避免这些理论上已经不存在的边的影响，我们将此档志愿的边全数删去（这意味着我们写的链式前向星要被升级为链表来支持快速删除）。

下面考虑第二问。第二问的思路也很简单，在第一问的残量网络上，倒着遍历每个人。当遍历到一个人时，先删去其第一问中连上的所有边，然后再把他前 s_i 档的边全数加入图中。跑最大流，找到那个新被匹配上的人，退流并删去其所有边，然后重新跑最大流，直到再也找不到新被匹配上的人。

这样就需要一些操作来保证正确性。具体而言，在删去第一问中的边时，同样，要先退流来消去影响，再删边。然后，为了保证不会有两个第二问的人同时匹配上了，却抢走了第一问的人的流量，我们必须保证任意时刻所有第二问的人中最多只能匹配一个。所以，我们要建立一个伪源点 s，连边 (S,s,1)，并且将所有第二问的人的边从 s 而非 S 连出。这样，即可保证所有第二问的人最多匹配一个。当Dinic下来发现最大流量增加时，找到 s 流向的那个节点，退流并删边，然后重新跑Dinic直到最大流量不再增加；否则，即最大流量没有增加，为了消除影响，我们对 s 退流（事实上，此处退流与否并不会影响算法正确性——因为最终方案中 s 也是要有流量的，但是这里代码中就随手写上了一次退流），然后进入前一个人的操作。

因为我们不需要像常规做法中一样支持前缀和残量网络的查询，所以空间复杂度是十分优秀的；然而，因为退流次数很多，所以实际消耗时间较常规做法甚至更劣，但是当数据范围更大时，此算法便会显著优于常规做法（因为少了二分以及拷贝前缀和残量网络等操作）。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,T_T,C_C,lim[210],acc[210],ide[210],imp[210];
namespace MaxFlow{
    const int N=510,M=1000000;
    int head[N],cur[N],dep[N],S,T,res;
    int bin[M],tp,cnt;//storing the id of edges
    int newedge(){return tp?bin[tp--]:cnt++;}//generating the id of an edge
    struct node{int to,next,last,val;}edge[M];//using a handwritten list to store edges
    int ae(int u,int v,int w){//adding an edge in the back, returning the id
        int U=newedge();
        edge[U].next=head[u],edge[U].last=-1,edge[U].to=v,edge[U].val=w;
        if(head[u]!=-1)edge[head[u]].last=U;head[u]=U;

        int V=newedge();
        edge[V].next=head[v],edge[V].last=-1,edge[V].to=u,edge[V].val=0;
        if(head[v]!=-1)edge[head[v]].last=V;head[v]=V;

        return U;//under every circumstance, V equals U+1. 
    }
    void ea(int U){//eliminating edge U
        int V=U+1,u=edge[V].to,v=edge[U].to;
        if(edge[V].next!=-1)edge[edge[V].next].last=edge[V].last;
        if(edge[V].last!=-1)edge[edge[V].last].next=edge[V].next;
        if(head[v]==V)head[v]=edge[V].next;
        bin[++tp]=V;

        if(edge[U].next!=-1)edge[edge[U].next].last=edge[U].last;
        if(edge[U].last!=-1)edge[edge[U].last].next=edge[U].next;
        if(head[u]==U)head[u]=edge[U].next;
        bin[++tp]=U;
    }
    queue<int>q;
    inline bool bfs(){
        memset(dep,0,sizeof(dep)),q.push(S),dep[S]=1;
        while(!q.empty()){
            register int x=q.front();q.pop();
            for(register int i=cur[x]=head[x];i!=-1;i=edge[i].next)if(edge[i].val&&!dep[edge[i].to])dep[edge[i].to]=dep[x]+1,q.push(edge[i].to);
        }
        return dep[T]>0;
    }
    bool reach;
    inline int dfs(int x,int flow){
        if(x==T){res+=flow,reach=true;return flow;}
        int used=0;
        for(register int &i=cur[x];i!=-1;i=edge[i].next){
            if(!edge[i].val||dep[edge[i].to]!=dep[x]+1)continue;
            register int ff=dfs(edge[i].to,min(edge[i].val,flow-used));
            if(ff){edge[i].val-=ff,edge[i^1].val+=ff,used+=ff;if(used==flow)break;}
        }
        return used;
    }
    inline void Dinic(int SS,int TT){S=SS,T=TT;while(bfs()){reach=true;while(reach)reach=false,dfs(S,0x3f3f3f3f);}}
}
using MaxFlow::head;
using MaxFlow::Dinic;
using MaxFlow::res;
using MaxFlow::edge;
using MaxFlow::cnt;
using MaxFlow::ae;
using MaxFlow::ea;
using MaxFlow::tp;
vector<int>v[210][210];
int read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
int S,T,s;//s is the pseudo source point. 
void compensate(int i){//conpensate for the influence of edge i.
    edge[i].val=0,edge[i+1].val=0;//blocking the supplying edge
    Dinic(T,edge[i].to);//eliminating the influence of the current operation, using backflowing
    edge[i].val=1,edge[i+1].val=0;//restore the supplying edge
} 
int e[210][210],sz[210];
int main(){
    T_T=read(),C_C=read();
    while(T_T--){
        n=read(),m=read(),memset(head,-1,sizeof(head)),cnt=res=tp=0,s=n+m+1,S=n+m+2,T=n+m+3;
        for(int i=1;i<=m;i++)ae(i+n,T,lim[i]=read());
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int x=read();if(x)v[i][x].push_back(j);}
        for(int i=1;i<=n;i++)ide[i]=read();
        for(int i=1;i<=n;i++){
            acc[i]=m+1,e[i][sz[i]=1]=ae(S,i,1);
            for(int j=1;j<=m;j++){
                for(auto k:v[i][j])e[i][++sz[i]]=ae(i,n+k,1);
                Dinic(S,T);
                if(res==i){acc[i]=j;break;}
                compensate(e[i][1]);
                res=i-1;//reset the answer
                while(sz[i]>1)ea(e[i][sz[i]--]);//reset the graph
            }
            res=i;//forcing the flow to i
        }
        for(int i=1;i<=n;i++)printf("%d ",acc[i]);puts("");
        int sor=ae(S,s,1);
        for(int i=n;i>=1;i--){
            imp[i]=i;
            compensate(e[i][1]),res=i-1;
            while(sz[i])ea(e[i][sz[i]--]);
            e[i][sz[i]=1]=ae(s,i,1);
            for(int j=1;j<=ide[i];j++)for(auto k:v[i][j])e[i][++sz[i]]=ae(i,n+k,1);
            while(true){
                Dinic(S,T);
                if(res==i-1){compensate(sor);break;}//inpossible to find one
                for(int k=head[s];k!=-1;k=edge[k].next)if(edge[k].to<=n&&!edge[k].val){
                    int x=edge[k].to;
                    compensate(k);
                    imp[x]=x-i,res=i-1;
                    while(sz[x])ea(e[x][sz[x]--]);
                    edge[sor].val=1,edge[sor^1].val=0;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++)printf("%d ",imp[i]);puts("");
        for(int i=1;i<=n;i++)sz[i]=0;
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)v[i][j].clear();
    }
    return 0;
}