思路
还是模板。
主要是有源汇之后,只有t和s不满足流量平衡,只要从t向s连一条下界是0,上界INF的边就变回无源汇的情况了
然后求出可行流流量(就是t到s的边的流量或者这条边反向边流量的相反数)后,再从s到t跑一遍最大流就能求出答案了(原来的可行流已被统计,剩下的s到t路径上能流过去的流也统计了)
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define int long long
using namespace std;
const int MAXN = 20100;
const int INF = 0x3f3f3f3f;
struct Edge{
int u,v,cap,flow;
};
vector<int> G[MAXN];
vector<Edge> edges;
int n,m,d[MAXN],sumx,lower[MAXN],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<G[x].size();i++){
Edge &e = edges[G[x][i]];
if(dep[e.v]==dep[x]+1&&(f=dfs(e.v,min(e.cap-e.flow,a),tx))>0){
flow+=f;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
a-=f;
if(!a)
break;
}
}
return flow;
}
queue<int> 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<G[x].size();i++){
Edge &e = edges[G[x][i]];
if((!vis[e.v])&&e.cap>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]);
}
addedge(t,s,INF,0);
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]);
}
}
int max_flow=dinic(ss,tt);
// printf("sumx=%lld maxflow=%lld\n",sumx,max_flow);
if(sumx==max_flow){
printf("%lld\n",dinic(s,t));
}
else{
printf("please go home to sleep\n");
}
return 0;
}