ECfinal 2019 E. Flow(假流真贪心）

Flow

叫flow结果和流没一点关系…

很坑,题意理解了半年

注意一句话叫做$图G是从1到n由相同长度的不相交路径组成的$

意味着如果一条$1$到$n$的路径是$x$,所以的路径都是长$x$

知道这个有什么用呢$?$显然可以计算得到最大流是$k=\frac{\sum flow}{x}$

其中$flow$表示边权

那么如果跑最大流,每条路径都会因为最小边限制流量

就算你给最小边拼命灌输流量,也会因为次小边限制流量…

所以我们把这条路径的边权小到大排序,越在前面越容易成为瓶颈

设想一下,当路径的第$i$小边成为瓶颈的时候,你需要给前$i$条边灌输流量才会使最大流增加$1$

这么一来就很明显了,我们不希望成为瓶颈的边太靠后,设一共有$p$条路径

我们可以枚举这$p$条路径在第$i$小边遇到了瓶颈(只给前$i$条边灌输流量)

这样一定是最优的,因为这样灌输的边是最少的

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=6e5+10; int n,m; struct edge{ int to,nxt,w; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v,int w){ d[++cnt]=(edge){v,head[u],w},head[u]=cnt; } int top; vector<int>v[maxn]; void dfs(int x) { if( x==n ) return; for(int i=head[x];i;i=d[i].nxt ) v[top].push_back(d[i].w),dfs(d[i].to); } int main() { cin >> n >> m; int res=0; for(int i=1;i<=m;i++) { int l,r,w; cin >> l >> r >> w; add(l,r,w); res+=w; } for(int i=head[1];i;i=d[i].nxt ) { v[++top].push_back(d[i].w); dfs(d[i].to); sort(v[top].begin(),v[top].end()); } res/=v[1].size(); int ans=0; for(int i=0;i<v[1].size();i++) { int temp=0; for(int j=1;j<=top;j++) temp+=v[j][i]; if( temp>=res ) break; ans+=res-temp; } cout << ans; }