EK
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<climits>
using namespace std;
#define N 10002
#define ff(a,b,c) for(int a=b;a<=c;a++)
typedef long long ll;
int n,m,s,t;
struct{
int u,v;ll w;
} edges[N];
int last[N];
ll flow[N];
int tot;
vector<int> to[N];
int exists[201][201];
inline void add_edge(int u,int v,ll w){
to[u].push_back(tot);
edges[tot++]={
u,v,w
};
}
bool bfs(){
queue<int> q;
memset(kast,0xFF,sizof(int)*(n+1));
flow[s]=LLONG_MAX;
q.push(s);
while(!q.empty()){
int cur=q.front();
q.pop();
if(cur==t) break;
for(auto e: to[cur]){
int v=edges[e].v;ll w=edges[e].w;
if(w>0&&last[v]==-1){
last[v]=e;
flow[v]=min(flow[cur], w);
q.push(v);
}
}
}
return last[t]!=-1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>s>>t;
ff(i,1,m){
int u,v;ll w;
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,0);
}
ll maxf=0;
while(bfs()){
maxf+=flow[t];
for(int i=t;i!=s;i=edges[last[i]].u){
int cur=last[i];
edges[cur].w -= flow[t];
edges[cur^1].w += flow[t];
}
}
cout<<maxf;
}
Dinic
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<climits>
using namespace std;
#define N 10002
#define ff(a,b,c) for(int a=b;a<=c;a++)
typedef long long ll;
int n,m,s,t;
struct{
int u,v;ll w;
} edges[N];
int dep[N];
int tot;
vector<int> to[N];
inline void add_edge(int u,int v,ll w){
to[u].push_back(tot);
edges[tot++]={
u,v,w
};
}
int fir[N];
ll dfs(int u,ll flow){
if(u==t||!flow) return flow;
ll curf=0;
for(auto i=to[u].begin()+fir[u];i!=to[u].end();i++){
int e=*i;
fir[u]++;
int v=edges[e].v;ll w=edges[e].w;
if(dep[v]!=dep[u]+1) continue;
ll f=dfs(v, min(w, flow-curf));
if(!f) continue;
curf+=f;
edges[e].w-=f;
edges[e^1].w+=f;
if(curf==flow) break;
}
return curf;
}
bool bfs(){
queue<int> q;
memset(dep,0,sizeof(int)*(n+1));
dep[s]=1;
q.push(s);
while(!q.empty()){
int cur=q.front();
q.pop();
for(auto e: to[cur]){
int v=edges[e].v;ll w=edges[e].w;
if(!dep[v]&&w>0){
dep[v]=dep[cur]+1;
q.push(v);
}
}
if(to[cur].size()) iter_swap(to[cur].begin(), to[cur].end()-1);
}
return dep[t]!=0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>s>>t;
ff(i,1,m){
int u,v;ll w;
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,0);
}
ll maxf=0;
while(bfs()){
memset(fir,0,sizeof(int)*(n+1));
maxf+=dfs(s,LLONG_MAX);
}
cout<<maxf;
}
费用流（基于Dinic）
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#define N 5005
#define M 100005
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
typedef struct{
int u,v;
int w,c;
} edge;
int tot;
int dis[N],vis[N];
edge edges[M];
vector<int> to[N];
inline void add_edge(int u,int v,int w,int c){
edges[tot]={
u,v,w,c
};
to[u].push_back(tot++);
}
typedef struct hi{
int c;int v;
bool operator <(const hi &x) const {
return c>x.c;
}
} hi;
int n,m,s,t;
int h[N];
void spfa(){
queue<int> q;
q.push(s);
memset(h,0x3F,sizeof(int)*(n+1));
memset(vis,0,sizeof(int)*(n+1));
h[s]=0;
vis[s]=1;
while(!q.empty()){
int cur=q.front();
q.pop();
vis[cur]=0;
for(auto e:to[cur]){
int v=edges[e].v,w=edges[e].w, c=edges[e].c,u=edges[e].u;
if(w&&h[v]>h[u]+c){
h[v]=h[u]+c;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
}
int last[N];
bool bfs(){
priority_queue<hi> q;
q.push({0,s});
memset(dis,0x3F,sizeof(int)*(n+1));
memset(vis,0,sizeof(int)*(n+1));
memset(last,0xFF,sizeof(int)*(n+1));
dis[s]=0;
while(!q.empty()){
auto k=q.top();
q.pop();
int cur=k.v;
if(vis[cur]) continue;
vis[cur]=1;
for(auto e:to[k.v]){
int v=edges[e].v,u=edges[e].u,c=edges[e].c;
if(edges[e].w&&dis[v]>dis[u]+c+h[u]-h[v]){
dis[v]=dis[u]+c+h[u]-h[v];
last[v]=e;
if(!vis[v]){
q.push({dis[v],v});
}
}
}
}
return last[t]!=-1;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int u,v;int w,c;
cin>>u>>v>>w>>c;
add_edge(u,v,w,c);
add_edge(v,u,0,-1*c);
}
spfa();
int maxflow=0,mincost=0;
while(bfs()){
int maxf=INF,cc=0;
for(int i=1;i<=n;i++) h[i]+=dis[i];
for(int i=last[t];i!=-1;i=last[edges[i].u]){
maxf=min(maxf, edges[i].w);
}
for(int i=last[t];i!=-1;i=last[edges[i].u]){
edges[i].w-=maxf;
edges[i^1].w+=maxf;
}
for(int i=last[t];i!=-1;i=last[edges[i].u]){
cc+=edges[i].c;
}
maxflow+=maxf;
mincost+=maxf*cc;
}
cout<<maxflow<<" "<<mincost;
}