ISAP+BFS初始化+栈优化
跑的飞快，但比较长
点数最大大概(10^5),边数最大大概(4 imes 10^5)
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 60050;
struct node {
int v, cap, flow, nxt;
node () {}
node (int v, int cap, int flow, int nxt): v(v), cap(cap), flow(flow), nxt(nxt) {}
} edge[N * 10];
int head[N], tot;
void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
int dep[N];
void adde(int u, int v, int w) {
edge[tot] = node(v, w, 0, head[u]);
head[u] = tot++;
edge[tot] = node(u, 0, 0, head[v]);
head[v] = tot++;
}
int gap[N], cur[N];
void bfs(int s, int t) {
memset(dep, -1, sizeof(dep));
memset(gap, 0, sizeof(gap));
gap[0] = 1;
queue<int> q;
dep[t] = 0;
q.push(t);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (dep[v] != -1) continue;
q.push(v);
dep[v] = dep[u] + 1;
gap[dep[v]]++;
}
}
}
int S[N];
int sap(int s, int t, int n) {
bfs(s, t);
memcpy(cur, head, sizeof(head));
int top = 0;
int u = s;
int ans = 0;
while (dep[s] < n) {
if (u == t) {
int minn = inf;
int inser;
for (int i = 0; i < top; i++) {
if (minn > edge[S[i]].cap - edge[S[i]].flow) {
minn = edge[S[i]].cap - edge[S[i]].flow;
inser = i;
}
}
for (int i = 0; i < top; i++) {
edge[S[i]].flow += minn;
edge[S[i] ^ 1].flow -= minn;
}
ans += minn;
top = inser;
u = edge[S[top] ^ 1].v;
continue;
}
bool flag = false;
int v;
for (int i = cur[u]; ~i; i = edge[i].nxt) {
v = edge[i].v;
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 minn = n;
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (edge[i].cap - edge[i].flow && dep[edge[i].v] < minn) {
minn = dep[edge[i].v];
cur[u] = i;
}
}
gap[dep[u]]--;
if (!gap[dep[u]]) return ans;
dep[u] = minn + 1;
gap[dep[u]]++;
if (u != s) u = edge[S[--top] ^ 1].v;
}
return ans;
}
普通ISAP 邻接表形式
跑的也挺快的，大概所需时间是dinic的2/3，无递归，可以完美替代dinic
点数最大大概(10^5),边数最大大概(4 imes 10^5)
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 20050;
struct node {
int v, cap, nxt;
node () {}
node (int v, int cap, int nxt): v(v), cap(cap), nxt(nxt) {}
} edge[N * 100];
int head[N], tot;
void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
int dep[N];
void adde(int u, int v, int w) {
edge[tot] = node(v, w, head[u]);
head[u] = tot++;
edge[tot] = node(u, 0, head[v]);
head[v] = tot++;
}
int cur[N];
int gap[N];
int pre[N];
int sap(int s, int t, int n) {
memset(dep, 0, sizeof(dep));
memset(gap, 0, sizeof(gap));
memcpy(cur, head, sizeof(head));
memset(pre, 0, sizeof(pre));
gap[0] = n;
int u = s;
pre[u] = -1;
int ans = 0;
while (dep[s] < n) {
if (u == t) {
int minn = inf;
for (int i = pre[u]; ~i; i = pre[edge[i ^ 1].v]) {
if (minn > edge[i].cap) minn = edge[i].cap;
}
for (int i = pre[u]; ~i; i = pre[edge[i ^ 1].v]) {
edge[i].cap -= minn;
edge[i ^ 1].cap += minn;
}
u = s;
ans += minn;
continue;
}
bool flag = false;
int v;
for (int i = cur[u]; ~i; i = edge[i].nxt) {
v = edge[i].v;
if (edge[i].cap && dep[v] + 1 == dep[u]) {
flag = true;
cur[u] = pre[v] = i;
break;
}
}
if (flag) {
u = v;
continue;
}
int minn = n;
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (edge[i].cap && dep[edge[i].v] < minn) {
minn = dep[edge[i].v];
cur[u] = i;
}
}
gap[dep[u]]--;
if (!gap[dep[u]]) return ans;
dep[u] = minn + 1;
gap[dep[u]]++;
if (u != s) u = edge[pre[u] ^ 1].v;
}
return ans;
}
还有一种递归写法，挺慢的，和dinic差不多，还不如dinic好写，没啥用。
Dinic
大部分时间够用，但普通ISAP只比dinic长10行，代码量相差不大。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 60050;
struct node {
int u, v, cap, nxt;
node () {}
node (int u, int v, int cap, int nxt): u(v), v(v), cap(cap), nxt(nxt) {}
} edge[N * 10];
int head[N], tot;
void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
int dep[N];
void adde(int u, int v, int w) {
edge[tot] = node(u, v, w, head[u]);
head[u] = tot++;
edge[tot] = node(v, u, 0, head[v]);
head[v] = tot++;
}
bool bfs(int s, int t) {
queue<int> q;
memset(dep, -1, sizeof(dep));
dep[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (edge[i].cap > 0 && dep[v] == -1) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t] > 0;
}
int dfs(int u, int t, int f) {//f是到这点的残余流量，used是这点已经流出的流量
if (u == t) return f;
int w, used = 0;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
int cap = edge[i].cap;
if (cap && dep[v] == dep[u] + 1) {
w = f - used;
w = dfs(v, t, min(w, cap));
edge[i].cap -= w;
edge[i ^ 1].cap += w;
used += w;
if (used == f) return f;
}
}
if (!used) dep[u] = -1;
return used;
}
int dinic(int s, int t) {
int maxflow = 0;
while (bfs(s, t)) {
maxflow += dfs(s, t, inf);
}
return maxflow;
}
最高标号预流推进(HLPP)
我觉得可能用不到把，复杂度是(n^2 sqrt{m})，但是常数比较大，和isap跑的差不多快
给个别人的板子，自己没写
#include <bits/stdc++.h>
using namespace std;
inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
const int inf=1<<30;
int top=1,head[10100];
int n,m,s,t;
int e[10100],h[10100],cnth[20100];//每个点对应的余流，高度；每个高度有多少个点
struct cmp{
inline bool operator () (int a,int b) const{
return h[a]<h[b];
}
};
struct Node{
int v;
int val;
int next;
}node[400100];
inline void addedge(int u,int v,int val){
node[++top].v=v;
node[top].val=val;
node[top].next=head[u];
head[u]=top;
}
inline void add(int u,int v,int val){
addedge(u,v,val);
addedge(v,u,0);
}
int inque[11000];
void bfs(){
memset(h,0x3f,sizeof(h));
h[t]=0;
queue<int>qu;
qu.push(t);
while(!qu.empty()){
int u=qu.front();
qu.pop();
inque[u]=0;
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(node[i^1].val&&h[d]>h[u]+1){//反向跑
h[d]=h[u]+1;
if(inque[d]==0){
qu.push(d);
inque[d]=1;
}
}
}
}
return;
}
priority_queue<int,vector<int>,cmp>q;
inline void push_(int u){
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(node[i].val&&h[d]+1==h[u]){//可以推流
int mi=min(node[i].val,e[u]);
node[i].val-=mi;
node[i^1].val+=mi;
e[u]-=mi;
e[d]+=mi;
if(inque[d]==0&&d!=t&&d!=s){
q.push(d);
inque[d]=1;
}
if(e[u]==0)break;//已经推完了
}
}
}//推流
inline void relabel(int u){
h[u]=inf;
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(node[i].val&&h[d]+1<h[u]){
h[u]=h[d]+1;
}
}
}//把u的高度更改为与u相邻的最低的点的高度加1
int hlpp(){
register int i;
bfs();
if(h[s]==0x3f3f3f3f)return 0;//s与t不连通
h[s]=n;
for(i=1;i<=n;i++)if(h[i]<0x3f3f3f3f)cnth[h[i]]++;//统计各个高度的点数，注意不要让下标越界
for(i=head[s];i;i=node[i].next){
int d=node[i].v;
int mi=node[i].val;
if(mi){
e[s]-=mi;
e[d]+=mi;
node[i].val-=mi;
node[i^1].val+=mi;
if(d!=t&&inque[d]==0&&d!=s){
q.push(d);
inque[d]=1;
}
}
}//从s向周围点推流
while(!q.empty()){
int u=q.top();
inque[u]=0;
q.pop();
push_(u);
if(e[u]){//还有余流
cnth[h[u]]--;
if(cnth[h[u]]==0){
for(int i=1;i<=n;i++){
if(i!=s&&i!=t&&h[i]>h[u]&&h[i]<n+1){
h[i]=n+1;//标记无法到达
}
}
}//gap优化
relabel(u);
cnth[h[u]]++;
q.push(u);
inque[u]=1;
}
}
return e[t];
}
int main(){
n=Read(),m=Read(),s=Read(),t=Read();
register int i;
int u,v,val;
for(i=1;i<=m;i++)u=Read(),v=Read(),val=Read(),add(u,v,val);
printf("%d",hlpp());
return 0;
}