2019EC E - Flow——贪心+规律

题目链接：http://codeforces.com/gym/102471/problem/E

题目大意：

给你n个点的一个简单图（即保证所有从1到n的路径上的点数都是相等的，且这些路径没有交点）

然后有一种操作，给一条边上的容量减一，另一条边的容量加一，问最少执行多少次操作使得从1到n的最大流最大。

题解：

这个题的关键在于读题，需要注意到这个图的特点。

首先我们不难想到图的最大流maxflow = 所有边的容量sum / 路径上的边的个数。

 然后我可以随意出几个数据，找一下规律。

不难发现规律就是：

对每一条路径的边按照容量从小到大排序。

然后依次枚举排序后路径上的边，

如果所有路径上第i小的边的容量和小于最大流，那么操作次数就是最大流减去容量和。

否则就直接跳出，因为这时肯定满足所有路径上最小边权值和等于最大流。

举个例子，假如图是这样的：

首先算出最大流就是 (1+2+3+4+5+6) / 3 = 7。

一种比较优的选择：

先把5->6这条边的权值挪4个到3->6这条边，这样保证最两个路径的最小值和为7（即最大流）

然后这样就保证了这个图的最大流为7。因为后面的边也都满足。

其实这个选择就是排序后发现，2+1<7,需要在这两个边任选一个边加4次才能保证最大流 。

因此就转换成了我们需要考虑每个路径上对应位置大小的边的权值和是否大于最大流。

这样也就能保证取的次数是最少的而且也是最大流。

代码实现：

#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#define PI atan(1.0)*4
#define E 2.718281828
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define debug printf("ac\n");
using namespace std;
inline int read()
{
    int a=0,b=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            b=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        a=(a<<3)+(a<<1)+c-'0';
        c=getchar();
    }
    return a*b;
}
const int INF = 0x3f3f3f3f;
const int N = 2e5+7;
struct Edge{
    int nxt,to,w;
}e[N];
int head[N],tot;
vector<int> G[N];
int cnt;
int n,m;
void addEdge(int u,int v,int w){
    e[++tot].to=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void dfs(int u,int fa){
    if(u==n) return ;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        G[cnt].pb(e[i].w);
        dfs(v,u);
    }
}
int main(){
    n=read(),m=read();
    ll flow=0;
    rp(i,1,m){
        int u=read(),v=read(),w=read();
        addEdge(u,v,w);
        flow+=w;
    }
    for(int i=head[1];i;i=e[i].nxt){
        int v=e[i].to;
        G[++cnt].pb(e[i].w);
        dfs(v,1);
        sort(G[cnt].begin(),G[cnt].end());
    }
    flow/=G[1].size();
    ll ans=0;
    rp(i,0,G[1].size()-1){
        ll sum=0;
        rp(j,1,cnt) sum+=G[j][i];
        if(sum>=flow) break;
        ans+=flow-sum;
    }
    printf("%lld",ans);
    return 0;
}