题解【CF847J Students Initiation】

传送门。

$\texttt{Description}$

有 $n$ 个人，$m$ 对关系，要求每对关系中，有且仅有一个人给另外一个人送礼物，并且使送出礼物最多的人送的礼物尽可能少。并输出送礼物的方案。

$1\le n,m\le 5\times 10^3$。

$\texttt{Solution}$

这翻译全都贺出去了，全都贺出去了啊

仍然考虑构造一个二分图。

一开始想了一个非常 $\texttt{naive}$ 的做法，左边是送礼物的人 $i$，右边对应是收礼物的人 $i'$。

对于一个关系 $(u,v)$，如果建边方式为 $u\to v'$ 和 $v\to u'$，且容量都为 $1$，则【有且仅有一个人给另外一个人送礼物】这个条件是无法表示出来的。

考虑左边还是送礼物的人，右边变成方案。

考虑将一个方案表示成一个点，对于第 $i$ 个方案，我们连边 $u_i\to i$，$v_i\to i$，容量均为 $1$，然后对于每一个方案与 $t$ 连一条容量为 $1$ 的边，这样就保证两个送出礼物最终只有一个能流到 $t$。

那么对于每一个人 $i$，$s$ 和 $i$ 之间如何连边呢？

看到了【最大值尽可能小】限制，很容易想到二分，我们二分每一个最多送出的礼物数量 $k$，所以对于每一个 $i$，连一条 $s\to i$，容量为 $k$ 的边。

最后输出只需要找那些残余流量为 $0$ 的边就行了。

还有一个大坑点，调了好久：每一次跑 $\text{dinic}$ 都是需要重新建图的，所以就导致，找到正确答案后，还会重新建一些新的图，这就导致找残余容量为 $0$ 的边会找错。

所以只需要找完答案后，重新建一遍图跑一个 $\text{dinic}$ 即可。

代码：

inline bool check(int k)
{
    remake();
    rep(i,1,m)
    {
        add_edge(nx[i],i+n,1);
        add_edge(ny[i],i+n,1);
    } 
    rep(i,1,n) add_edge(s,i,k);
    rep(i,1,m) add_edge(i+n,t,1);
    int ans(0);
    while(bfs()) ans+=dfs(s,INF);
    return ans==m&&ans;
}
int main()
{
    n=read(),m=read();
    rep(i,1,m) nx[i]=read(),ny[i]=read();
    int l=1,r=n,res(0);
    s=0,t=n+m+1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,res=mid;
        else l=mid+1; 
    }
    printf("%d\n",res);
    check(res);
    rep(i,1,m)
    {
        bool flag(false);
        gra(j,nx[i]) if(edge[j].to==i+n&&!edge[j].flow)
        {
            printf("%d %d\n",nx[i],ny[i]);
            flag=true;
            break;
        }
        if(!flag) printf("%d %d\n",ny[i],nx[i]);
    }
    return 0;
}

$$\texttt{The End.by UF}$$