自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 23:00:22，当前版本为作者最后更新于2024-08-15 17:43:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$\text{Link}$

题意

给定一个 $n$ 个点 $m$ 条边的单位网络，保证该网络不存在环。给定一个常数 $k$，设从 $1$ 到 $i$ 的最大流为 $f_i$，对 $\forall i\in[2,n]$ 求出 $\min(f_i,k)$。

$n\le 10^5$，$m\le 2\times10^5$，$k\le\min(n-1,50)$。

思路

不相交路径，考虑 LGV 引理。但此处不相交路径只要求边不相交，于是我们把边看成点，每个点的所有入边向所有出边连边，这样边不相交便转化为了点不相交。

从 P9041 我们了解到，该问题的解法为给每条边随机赋上 $[0,P)$ 的权值，则起点集合 $s_{1\dots x}$ 到终点集合 $t_{1\dots y}$ 的答案就是矩阵 $e_{s_i,t_j}(i\in[1,x],j\in[1,y])$ 的秩。

我们现在需要解决两个问题：

1. 起点集合（即 $1$ 的所有出边）可能很大。我们新建源点 $s$ 和 $k$ 个虚点 $p_{1\dots k}$，连边 $s\to p_i,p_i\to t$ 即可，其中 $t$ 为 $1$ 的任意出点。于是起点集合的大小被我们减小到了 $O(k)$。
2. 如果一个点的入度出度均较大，那么这个点的入边出边之间的边数会很大。注意到这些边都会随机赋一个权，相当于每个出边对应的向量为所有入边对应的向量的随机线性组合。于是对于入边，我们只需要保留线性无关的不超过 $k$ 组向量即可，这个任务可以交给线性基解决。

总时间复杂度 $O((n+m)k^2)$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
    
}
namespace rad{
    mt19937_64 R(chrono::system_clock::now().time_since_epoch().count());
    inline int Rand(int l,int r){
        uniform_int_distribution<int> distribution(l,r);
        return distribution(R);
    }
}using namespace rad;
const int N=1e5+10,K=50+2,mod=1e9+9;
namespace PolyC{
    #define Poly vector<int>
    inline int qpow(int x,int y){
        int res=1;
        while(y){
            if(y&1) res=1ll*res*x%mod;
            x=1ll*x*x%mod;
            y>>=1;
        }
        return res;
    }
    inline int add(int a,int b){
        return a+b>=mod?a+b-mod:a+b;
    }
    inline int dec(int a,int b){
        return a>=b?a-b:a+mod-b;
    }
    inline Poly operator+(const Poly &a,const Poly &b){
        Poly F=a;
        F.resize(max(a.size(),b.size()));
        for(int i=0;i<b.size();i++)
            F[i]=add(F[i],b[i]);
        return F;
    }
    inline Poly operator-(const Poly &a,const Poly &b){
        Poly F=a;
        F.resize(max(a.size(),b.size()));
        for(int i=0;i<b.size();i++)
            F[i]=dec(F[i],b[i]);
        return F;
    }
    inline Poly operator*(const Poly &a,const int &b){
        Poly F=a;
        for(int i=0;i<F.size();i++)
            F[i]=1ll*F[i]*b%mod;
        return F;
    }
}
using namespace PolyC;
int n,m,k,d[N];
Poly ct[N];
vector<int>a[N];
struct LnB{
	int c;
    bool vs[K];
    Poly v[K];
    inline void ins(Poly vt){
        for(int i=0;i<k;i++){
            if(!vt[i]) continue;
            if(!vs[i]){
                vs[i]=1,v[i]=vt,c++;
                return ;
            }else{
                int b=1ll*qpow(v[i][i],mod-2)*vt[i]%mod;
                vt=vt-v[i]*b;
            }
        }
    }
}L[N];
inline void bfs(){
    queue<int>q;
    for(int t:a[1]){
    	Poly X(k,0);
    	for(int i=0;i<k;i++)
    		X[i]=Rand(1,mod-1);
    	L[t].ins(X),d[t]--;
	}
    for(int i=2;i<=n;i++)
        if(!d[i])
            q.push(i);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vector<Poly>vc;
        for(int i=0;i<k;i++)
        	if(L[x].vs[i])
        		vc.push_back(L[x].v[i]);
        for(auto t:a[x]){
            Poly X(k,0);
            for(auto I:vc)
            	X=X+I*Rand(1,mod-1);
            L[t].ins(X);
            if(!--d[t]) q.push(t);
        }
    }
}
int main(){
    n=read(),m=read(),k=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        a[u].push_back(v),d[v]++;
    }
    for(int i=1;i<=n;i++)
        ct[i].resize(k);
    bfs();
    for(int i=2;i<=n;i++)
        write(L[i].c),putc(' ');
	flush();
}