Educational Codeforces Round 55 (Rated for Div. 2) G. Petya and Graph 网络流|

很经典，想记录一下

网络流里有一个很典的trick，求最大获利转化成最小损失

求最小损失转化成割边

求的是max(边权和-边所连接的点权和)，考虑把边看成左部点，把点看成右部点

刚开始我们假设边全都要选，那么最小割也就是选取左部所有点，去掉右边所有点

也就是把所有边都选了，再扣掉所有点（根据最小割的意义）

然后考虑不要某些项目，我们可以割s和该项目连的边，表示不要这个获利

那跑个最小割，输出时用sigma(wi)-最小割即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50000;
const ll inf=LONG_LONG_MAX;
struct lys{
    ll from,to,nxt,c;
}e[maxn*4];
ll cnt=1,n,m,s,t,dep[maxn],head[maxn],val[maxn],cur[maxn];
void add(int from,int to,ll c)
{
    cnt++;
    e[cnt].from=from;e[cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;val[cnt]=c;
}

bool  bfs()
{   queue<int>q;
    memset(dep,0,sizeof(dep));
    q.push(s);
    dep[s]=1;
    cur[s]=head[s];
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int to=e[i].to;
            if(val[i]&&!dep[to])
            {
                dep[to]=dep[u]+1;
                cur[to]=head[to];
                q.push(to);
            }
        }
    }
    return dep[t];    
}
ll dfs(int u,ll in)
{
    if(u==t) 
    return in;
    ll out=0;
    for(int i=cur[u];i&&in;i=e[i].nxt)
    {
      cur[u]=i;
      int to=e[i].to;
      if(val[i]&&dep[to]==dep[u]+1)
      {
          ll res=dfs(to,min(val[i],in));
          val[i]-=res;
          val[i^1]+=res;
          in-=res;
          out+=res;
      }    
    }
    
    if(!out) 
      dep[u]=0;
    return out;
}
int a[maxn];
int main()
{  // freopen("lys.in","r",stdin);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    s=0;
    t=n+m+1;
    ll sum=0;
    for(int i=1;i<=m;i++){
        int u,v;ll w;cin>>u>>v>>w;
        sum+=w;
        u+=m;v+=m;
        add(i,u,inf);
        add(u,i,0);
        add(i,v,inf);
        add(v,i,0);
        add(s,i,w);
        add(i,s,0); 
    }
    for(int i=1;i<=n;i++) add(i+m,t,a[i]),add(t,i+m,0);
    ll ans=0;
    while(bfs())     ans+=dfs(s,1e18);
    cout<<sum-ans;
}