dinic
代码：
#include <bits/stdc++.h>
#define maxn 100000
#define inf 99999999
using namespace std;
struct edge{int from,to,cap,flow;};
struct dinic{
int n,m,s,t;
vector<edge> edges;
vector<int> g[maxn];
bool vis[maxn];
int d[maxn];
void arr(int from,int to,int cap)
{
edges.push_back((edge){from,to,cap,0});
edges.push_back((edge){to,from,0,0});
m=edges.size();
g[from].push_back(m-2);
g[to].push_back(m-1);
}
bool bfs() {
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(s);
d[s]=0;
vis[s]=1;
while (q.empty()==false)
{
int x=q.front(); q.pop();
for (int i=0;i<g[x].size();i++)
{
edge e=edges[g[x][i]];
if (!vis[e.to] && e.cap>e.flow)
{
vis[e.to]=1;
d[e.to]=d[x]+1;
q.push(e.to);
}
}
}
return(vis[t]);
}
int dfs(int x,int a)
{
if (x==t || a==0) return a;
int flow=0,f;
for (int i=0;i<g[x].size();i++)
{
edge &e=edges[g[x][i]];
if (d[x]+1==d[e.to] && (f=dfs(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
edges[g[x][i]^1].flow-=f;
flow+=f;
a-=f;
if (a==0) break;
}
}
return(flow);
}
int maxflow(int s,int t)
{
this->s=s; this->t=t;
int flow=0;
while (bfs())
{
flow+=dfs(s,inf);
}
return(flow);
}
}di;
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
int n,m,s,t;
cin>>n>>m>>s>>t;
for (int i=1;i<=m;i++)
{
int from,to,cap;
cin>>from>>to>>cap;
di.arr(from,to,cap);
}
cout<<di.maxflow(s,t);
}
#include <bits/stdc++.h> using namespace std; const int maxn=3e5; #define INF 1e9 int n,m,s,t,l; int head[maxn],d[maxn]; bool vis[maxn]; struct re{ int a,b,c,flow; }a[maxn]; void arr(int x,int y,int z) { a[++l].a=head[x]; a[l].b=y; a[l].c=z; head[x]=l; } bool bfs(){ memset(vis,0,sizeof(vis)); queue<int> q; q.push(s); d[s]=0; vis[s]=1; while (!q.empty()) { int x=q.front();q.pop(); int u=head[x]; while (u) { int v=a[u].b; if (!vis[v]&&a[u].c>a[u].flow) { vis[v]=1; d[v]=d[x]+1; q.push(v); } u=a[u].a; } } return(vis[t]); } int dfs(int x,int y) { if (x==t||y==0) return y; int flow=0,f,tmp; int u=head[x]; while (u) { int v=a[u].b; if (d[x]+1==d[v]&&(f=dfs(v,min(y,a[u].c-a[u].flow)))>0) { a[u].flow+=f; if (u%2) tmp=u+1; else tmp=u-1; a[tmp].flow-=f; flow+=f; y-=f; if (y==0) break; } u=a[u].a; } return(flow); } int maxflow(int s,int t) { int flow=0; while (bfs()) { flow+=dfs(s,INF); } return(flow); } int main() { cin>>n>>m>>s>>t; for (int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; arr(x,y,z); arr(y,x,0); } cout<<maxflow(s,t); }
最小费用最大流：
#include <bits/stdc++.h>
using namespace std;
#define maxn 100100
#define INF 1e9
int d[maxn],p[maxn],aa[maxn],l,head[maxn],n,m,s,t;
bool inq[maxn];
struct re{
int a,b,c,from,flow,cost;
}a[maxn];
void arr(int x,int y,int z,int flow,int cost)
{
a[++l].a=head[x];
a[l].b=y;
a[l].c=z;
a[l].flow=flow;
a[l].cost=cost;
a[l].from=x;
head[x]=l;
}
bool bellmanford(int &flow,int &cost){
for (int i=1;i<=n;i++) d[i]=INF;
memset(inq,0,sizeof(inq));
d[s]=0; inq[s]=1; p[s]=0; aa[s]=INF;
queue<int>q;
q.push(s);
while (!q.empty())
{
int x=q.front();q.pop(); inq[x]=0;
int u=head[x];
while (u)
{
int v=a[u].b;
if(a[u].c>a[u].flow&&d[v]>d[x]+a[u].cost){
d[v]=d[x]+a[u].cost;
p[v]=u;
aa[v]=min(aa[x],a[u].c-a[u].flow);
if (!inq[v]){
q.push(v);inq[v]=1;
}
}
u=a[u].a;
}
}
if (d[t]==INF) return(false);
flow+=aa[t];
cost+=d[t]*aa[t];
int x=t;
while (x!=s)
{
int u=p[x];
a[u].flow+=aa[t];
if (u%2) a[u+1].flow-=aa[t]; else a[u-1].flow-=aa[t];
x=a[u].from;
}
return true;
}
int flow,cost;
void mincost()
{
while (bellmanford(flow,cost));
}
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
cin>>n>>m>>s>>t;
int c,d,e,f;
for (int i=1;i<=m;i++)
{
cin>>c>>d>>e>>f;
arr(c,d,e,0,f); arr(d,c,0,0,-f);
}
mincost();
cout<<flow<<" "<<cost;
}