题解：P10698 [SNCPC2024] 最大流
cyffff
·
·
题解
\text{Link}
题意
给定一个 n 个点 m 条边的单位网络，保证该网络不存在环。给定一个常数 k，设从 1 到 i 的最大流为 f_i，对 \forall i\in[2,n] 求出 \min(f_i,k)。
## 思路
不相交路径，考虑 LGV 引理。但此处不相交路径只要求边不相交，于是我们把边看成点，每个点的所有入边向所有出边连边，这样边不相交便转化为了点不相交。
从 [P9041](https://www.luogu.com.cn/problem/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)$。
参考代码：
```cpp
#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();
}
```