2019 ICPC EC Final E（思维）
90nwyn
2020-10-05 18:31:14
[题目链接](https://vjudge.net/problem/Gym-102471E)
------------
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
const int M=4e5+5;
typedef long long ll;
int n,m,head[M],nxt[M],ver[M],tot,len;
ll edge[M],flow,addflow[M],ans;
vector<ll> vt;
void add(int x,int y,ll z)
{
nxt[++tot]=head[x];
head[x]=tot;
ver[tot]=y;
edge[tot]=z;
}
void dfs(int x)
{
for(int i=head[x];i;i=nxt[i])
{
vt.push_back(edge[i]);
dfs(ver[i]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;ll z;scanf("%d%d%lld",&x,&y,&z);
add(x,y,z);
flow+=z;
}
for(int i=head[1];i;i=nxt[i])
{
vt.clear();
vt.push_back(edge[i]);
dfs(ver[i]);
sort(vt.begin(),vt.end());
len=vt.size();
for(int j=0;j<len-1;j++)addflow[j+1]+=vt[j+1]-vt[j];
flow-=vt[0]*len;
}
for(int i=1;i<len;i++)
{
if(flow<len)break;
ll tmp=min(addflow[i],flow/len);
ans+=tmp*i;
flow-=tmp*len;
}
printf("%lld\n",ans);
return 0;
}
```