思路

首先加上t-s的边跑最大流

设d是加上的边的流量，删掉加上的边

答案是d-maxflow(t,s)

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define int long longusing namespace std;const int MAXN = 50100;const int INF = 0x3f3f3f3f;struct Edge{    int u,v,cap,flow;};vector
         
           G[MAXN];vector
          
            edges;int n,m,d[MAXN],sumx,lower[200000],ss,tt,vis[MAXN],dep[MAXN],cur[MAXN],s,t;void addedge(int u,int v,int cap){ edges.push_back((Edge){u,v,cap,0}); edges.push_back((Edge){v,u,0,0}); int cnt=edges.size(); G[u].push_back(cnt-2); G[v].push_back(cnt-1);}void addedge(int u,int v,int cap,int lower){ addedge(u,v,cap-lower); d[u]+=lower; d[v]-=lower; }int dfs(int x,int a,int tx){ if(x==tx||a==0) return a; int flow=0,f; for(int &i=cur[x];i
           
            0){ flow+=f; e.flow+=f; edges[G[x][i]^1].flow-=f; a-=f; if(!a) break; } } return flow;}queue
            
              q;bool bfs(int sx,int tx){ memset(vis,0,sizeof(vis)); dep[sx]=0; q.push(sx); vis[sx]=1; while(!q.empty()){ int x=q.front(); q.pop(); for(int i=0;i
             
              e.flow){ dep[e.v]=dep[x]+1; vis[e.v]=true; q.push(e.v); } } } return vis[tx];}int dinic(int sx,int tx){ int flow=0; while(bfs(sx,tx)){ memset(cur,0,sizeof(cur)); flow+=dfs(sx,INF,tx); } return flow;}signed main(){ // freopen("1.in","r",stdin); // freopen("1.out","w",stdout); scanf("%lld %lld %lld %lld",&n,&m,&s,&t); for(int i=1;i<=m;i++){ int a,b,c; scanf("%lld %lld %lld %lld",&a,&b,&lower[i],&c); addedge(a,b,c,lower[i]); } ss=MAXN-2; tt=MAXN-3; for(int i=1;i<=n;i++){ if(d[i]>0){ addedge(i,tt,d[i]); sumx+=d[i]; } else{ addedge(ss,i,-d[i]); } } addedge(t,s,INF,0); int max_flow=dinic(ss,tt); // printf("sumx=%lld maxflow=%lld\n",sumx,max_flow); if(sumx==max_flow){ int d=edges[G[t][G[t].size()-1]].flow; G[s].pop_back(); G[t].pop_back(); printf("%lld\n",d-dinic(t,s)); } else{ printf("please go home to sleep\n"); } return 0;}