自动搬运

查看原文

来自洛谷，原作者为

	TheAutumnGlory QQ:1945881313

搬运于2025-08-24 22:14:22，当前版本为作者最后更新于2020-02-23 16:21:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题肯定用网络流，不然$nodgd$给你放在网络流考试里干嘛

题意：

给了一个有向无环图，给（除了根节点）每个节点选一条出边构成一棵树，让儿子个数最多的节点的儿子个数最少。（根节点不算） 依次输出每个节点的父亲，要求字典序最小。

先不考虑字典序，考虑计算最小的负载级别。

很显然想到负载级别可以用二分答案来求。

判断负载级别为K是否可行，于是我们可以建出这样一幅图来：

然后计算最大流，如果最大流=$N$，说明负载级别可以等于$K$

那么如何验证字典序最小呢？

枚举

在过程中，我们已经确定了$fa[0]$~$fa[i-1]$，此时枚举$fa[i]$，$fa[i+1]$~$fa[n-1]$未确定。

那么$0$~$i-1$节点只和已确定的父亲连边，$i$号节点也和枚举的父亲连边，$i+1$~$n-1$按原来的方式连边（可能有多条）。

如果当前$fa[i]$建图跑最大流=n，说明当前$fa[i]$可行，$fa[i]$就定下来枚举$i+1$

如果最大流$<N$，说明不行，继续枚举$i$的出边作为$fa[i]$，继续验证即可

要跑$N^2$次网络流，可以过，但是$nodgd$觉得他不够优秀。

优化（跑$NlogN$次最大流）

刚才，枚举$i$的出边作为$fa[i]$

现在：网络流验证 $L \leq fa[i] \leq R$ 是否可行

于是$i$号节点就和$L$~$R$连边

就可以二分验证

一开始已知在$[0,N]$有解

第一轮就验证$[0,N/2]$

第二轮...

其实也快不到那里去...

$code:$

#include<bits/stdc++.h>
using namespace std;
const int N=205;
const int M=5005;
const int inf=1e9;
int n,k,S,T,fa[N];
char a[N][N];
int Last[N],Next[M],End[M],len[M],tot;
int _last[N],dis[N],gap[N];
void cb(int x,int y,int z,int z0=0){
    End[tot]=y,Next[tot]=Last[x],len[tot]=z,Last[x]=tot++;
    End[tot]=x,Next[tot]=Last[y],len[tot]=z0,Last[y]=tot++;
}
void bfs(){
    for(int i=1;i<=T;i++) dis[i]=T,gap[i]=0;
    gap[0]=0;
    dis[T]=0;
    queue<int> q;
    q.push(T);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=Last[x];i;i=Next[i]){
            int y=End[i];
            if(dis[y]>dis[x]+1){
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    for(int i=1;i<=T;i++) gap[dis[i]]++,_last[i]=Last[i];
}
int isap(int x,int flow){
    if(x==T) return flow;
    int flow_now=0;
    for(int &i=_last[x];i;i=Next[i]){
        int y=End[i];
        if(len[i] && dis[x]==dis[y]+1){
            int f=isap(y,min(len[i],flow-flow_now));
            flow_now+=f;
            len[i]-=f;
            len[i^1]+=f;
            if(flow==flow_now || dis[S]==T) return flow_now;
        }
    }
    gap[dis[x]]--;
    if(gap[dis[x]]==0) dis[S]=T;
    dis[x]++;
    gap[dis[x]]++;
    _last[x]=Last[x];
    return flow_now;
}
bool check(int mid){
    S=2*n+1;
    T=S+2;
    tot=2;
    for(int i=1;i<=n;i++){
        cb(S,i,1);
        if(fa[i]) cb(i,fa[i]>n?T:fa[i]+n,1);
        else if(a[0][i]=='Y') cb(i,T,1);
        else
            for(int j=1;j<=n;j++)
                if(a[i][j]=='Y')
                    cb(i,j+n,1);
        cb(i+n,T,mid);
    }
    int res=0;
    bfs();
    while(dis[S]<T) res+=isap(S,inf);
    for(int i=0;i<=T;i++) Last[i]=0;
    if(res==n) return 1;
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<=n;i++) scanf("%s",a[i]+1);
    for(int i=1;i<=n;i++) a[i][n+1]=a[0][i];
    int l=0,r=n;
    //------
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid-1;
            k=mid;
        }
        else l=mid+1;
    }
    //------
    for(int i=1;i<=n;i++){
        bool flag=0;
        for(int j=1;j<=n;j++){
            if(a[i][j]=='Y'){
                fa[i]=j;
                if(check(k)){
                    flag=1;
                    break;
                }
            }
        }
        if(flag) continue;
        fa[i]=n+1;//fa[i]=CC
    }
    //------
    for(int i=1;i<=n;i++) printf("%d ",fa[i]-1);
    return 0;
}