有源汇最大流
<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;
void init(){
tol = 0;
memset(head, -1, sizeof(head));
}
namespace Nflows{
int gap[maxn], dep[maxn], cur[maxn];
int Q[maxn], s[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){//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;
}
ll 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;
}
}
int n, m;
int main(){
while(scanf("%d%d", &n, &m) == 2) {
init();
for(int i = 1; i <= n ;i++){
int u, v;
ll w;
cin >> u >> v >> w;
Nflows::addedge(u, v, w);
}
cout << Nflows::isap(1, m, m) << endl;
}
}</code></pre>