题意：
给出一张特殊的图，每次可以让一条边的容量+ 1，另一条边的容量− 1，使得最大流最大，求最小操作次数。
特殊在于：
起点到终点的路径不相交且长度相同且路径上的点无重复
思路：
由于所有路径的长度都相同，所以最大流等于所 有 边 的 容 量 之 和 路 径 长 度 \frac{所有边的容量之和}{路径长度}
路径长度
所有边的容量之和。这里的最大流指的是每一层的流量，也就是所有路径第k条边的流量之和。
对于路径的边来说，每条边都应该大于等于最大流，所以对于小于最大流的边来说，差值的累计就是代价。排序后，对于每一层的流量总和，如果小于最大流的话，就计入答案。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define debug(x) cout<<#x<<":"<<x<<endl; const int maxn=2e5+100; int h[maxn],idx,e[maxn],ne[maxn]; ll w[maxn],n,m,sum=0,pre[maxn]; vector<ll>v; void add(int u,int v,ll ww){ e[idx]=v,ne[idx]=h[u],w[idx]=ww;h[u]=idx++; } void dfs(int u){ if(u==n) return ; for(int i=h[u];i!=-1;i=ne[i]){ v.push_back(w[i]); dfs(e[i]); } } int main(){ cin>>n>>m; memset(h,-1,sizeof h); for(int i=1;i<=m;i++){ int u,v; ll ww; cin>>u>>v>>ww; add(u,v,ww); sum=sum+ww; } int len=-1; for(int i=h[1];i!=-1;i=ne[i]){ int j=e[i]; v.clear(); v.push_back(w[i]); dfs(j); len=v.size(); sort(v.begin(),v.end()); int now=1; // debug(j); for(auto t:v){ pre[now]+=t; // cout<<t<<" "; now++; } // puts(""); } ll cor=sum/len,ans=0; //debug(cor); // debug(len) for(int i=1;i<=len;i++){ if(pre[i]<cor) ans=ans+cor-pre[i]; // debug(pre[i]); } cout<<ans<<endl; return 0; }
