有源汇上下界最大流
<pre><code class="language-cpp">#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int maxm = 4e5+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct Edge{
int to;
int next;
ll cap;
ll flow;
};
Edge edge[maxm];
int head[maxn];
int tol;
namespace ULNflows_max{
int gap[maxn], dep[maxn], cur[maxn];
int Q[maxn], s[maxn];
ll more[maxn];
void addedge(int u, int v, ll w, ll rw = 0){
edge[tol].to = v;
edge[tol].cap = w;
edge[tol].flow = 0;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = rw;
edge[tol].flow = 0;
edge[tol].next = head[v];
head[v] = tol++;
}
void bfs(int start, int end){
memset(dep, -1, sizeof(dep));
memset(gap, 0, sizeof(gap));
gap[0] = 1;
int front = 0, rear = 0;
dep[end] = 0;
Q[rear++] = end;
while(front != rear){
int u = Q[front++];
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(dep[v] != -1) continue;
Q[rear++] = v;
dep[v] = dep[u] + 1;
gap[dep[v]]++;
}
}
}
ll isap(int start, int end, int n){//起点，终点，点的个数
bfs(start, end);
memcpy(cur, head, sizeof(head));
int top = 0;
int u = start;
ll ans = 0;
while(dep[start] < n){
if(u == end){
ll Min = INF;
int inser;
for(int i = 0; i < top; i++){
if(Min > edge[s[i]].cap - edge[s[i]].flow){
Min = edge[s[i]].cap - edge[s[i]].flow;
inser = i;
}
}
for(int i = 0; i < top; i++){
edge[s[i]].flow += Min;
edge[s[i]^1].flow -= Min;
}
ans += Min;
top = inser;
u = edge[s[top]^1].to;
continue;
}
bool flag = false;
int v;
for(int i = cur[u]; i != -1; i = edge[i].next){
v = edge[i].to;
if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]){
flag = true;
cur[u] = i;
break;
}
}
if(flag){
s[top++] = cur[u];
u = v;
continue;
}
int Min = n;
for(int i = head[u]; i != -1; i = edge[i].next){
if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){
Min = dep[edge[i].to];
cur[u] = i;
}
}
gap[dep[u]]--;
if(!gap[dep[u]]) return ans;
dep[u] = Min + 1;
gap[dep[u]]++;
if(u != start) u = edge[s[--top]^1].to;
}
return ans;
}
}
void init(){
tol = 0;
memset(head, -1, sizeof(head));
memset(ULNflows::more, 0, sizeof(ULNflows::more));
}
int n, m;
int main(){
init();
int s, t;
scanf("%d%d%d%d", &n, &m, &s, &t);
int ss = n+1, tt = n+2;
for(int i = 1; i <= m; i++){
int u, v;
ll up, low;
scanf("%d%d%lld%lld", &u, &v, &low, &up);
ULNflows::addedge(u, v, up-low);
ULNflows::more[u] -= low;
ULNflows::more[v] += low;
}
ll maxflow = 0;
for(int i = 1; i <= n; i++){
if(ULNflows::more[i] > 0) ULNflows::addedge(ss, i, ULNflows::more[i]), maxflow += ULNflows::more[i];
else if(ULNflows::more[i] < 0) ULNflows::addedge(i, tt, -ULNflows::more[i]);
}
ULNflows::addedge(t, s, INF);
if(maxflow == ULNflows::isap(ss, tt, n+2)){
cout << ULNflows::isap(s, t, n+2) << endl;
}else{
cout << "-1";
}
}</code></pre>