Flow

The first line contains two integers ${n}$ and ${m}$ ( $2\leq n\leq 100000, 1\leq m \leq 200000$ ).
Each of the next ${m}$ lines contains three integers ${x, y}$ and ${z}$ , denoting an edge from ${x}$ to ${y}$ with capacity ${z}$ ( $1 \leq x, y \leq n$ , $0\le z\le 1000000000$ ).
It's guaranteed that the input is a universe graph without multiple edges and self-loops.

C++14(g++5.4) 解法, 执行用时: 124ms, 内存消耗: 15384K, 提交时间: 2020-01-12 19:47:13

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=N<<1;
int n,m,flow,res,cnt;
int head[N],nex[M],to[M],w[M],tot;
vector<int> v[N];
inline void add(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
void dfs(int x){
	if(x==n)	return ;
	for(int i=head[x];i;i=nex[i]){
		v[cnt].push_back(w[i]);	dfs(to[i]);
	}
}
signed main(){
	ios::sync_with_stdio(false);	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1,a,b,c;i<=m;i++)	cin>>a>>b>>c,add(a,b,c),flow+=c;
	for(int i=head[1];i;i=nex[i]){
		v[++cnt].push_back(w[i]); dfs(to[i]);
		sort(v[cnt].begin(),v[cnt].end());
	}
	flow/=v[1].size();
	for(int i=0,s;i<v[1].size();i++){
		s=0;
		for(int j=1;j<=cnt;j++)	s+=v[j][i];
		if(s>=flow)	break;
		res+=flow-s;
	}
	cout<<res;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 234ms, 内存消耗: 14976K, 提交时间: 2020-02-19 16:54:04

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=1e5+10;

int n,m,k;

vector< pair<ll,ll> >g[maxn];
vector<int> a[maxn];

void dfs( int x )
{
	if( x==n ) 
	{
		sort(a[k].begin(),a[k].end());
		return;
	}
	for( auto v:g[x] )
	{
		if( x==1 ) k++;
		a[k].push_back( v.second );
		dfs( v.first );
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	ll avg=0;
	for( int i=0;i<m;i++ )
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back( make_pair(v,w) );
		avg+=w;
	}
	k=0;
	dfs(1);
	
	ll ans=0;
	avg/=a[1].size(); // 最大流量 
	for( int i=0;i<a[1].size();i++ )
	{
		ll tmp=0;
		for( int j=1;j<=k;j++ ) tmp+=a[j][i];
		if( tmp>=avg ) break;   
		ans+=avg-tmp;  // 操作次数 
	}
	printf("%lld\n",ans);
}

详情