最大流dinic板子
const int N = 1e6+10, S = N-2, T = N-1, INF = 0x3f3f3f3f;
int n;
struct edge {
int to,w,next;
edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
int bfs() {
REP(i,1,n) dep[i]=INF,vis[i]=0,cur[i]=head[i];
dep[S]=INF,vis[S]=0,cur[S]=head[S];
dep[T]=INF,vis[T]=0,cur[T]=head[T];
dep[S]=0,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
for (int i=head[u]; i; i=e[i].next) {
if (dep[e[i].to]>dep[u]+1&&e[i].w) {
dep[e[i].to]=dep[u]+1;
Q.push(e[i].to);
}
}
}
return dep[T]!=INF;
}
int dfs(int x, int w) {
if (x==T) return w;
int used = 0;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].to]==dep[x]+1&&e[i].w) {
int f = dfs(e[i].to,min(w-used,e[i].w));
if (f) used+=f,e[i].w-=f,e[i^1].w+=f;
if (used==w) break;
}
}
return used;
}
int dinic() {
int ans = 0;
while (bfs()) ans+=dfs(S,INF);
return ans;
}
void add(int u, int v, int w) {
e[++cnt] = edge(v,w,head[u]);
head[u] = cnt;
e[++cnt] = edge(u,0,head[v]);
head[v] = cnt;
}
费用流EK+spfa板子
const int N = 1e6+10, INF = 0x3f3f3f3f, S = N-2, T = N-1;
int n, m, flow, cost;
struct edge {
int to,w,v,next;
edge(int to=0,int w=0,int v=0,int next=0):to(to),w(w),v(v),next(next){}
} e[N];
int head[N], dep[N], vis[N], cur[N], f[N], cnt=1;
int pre[N],pre2[N];
queue<int> Q;
int spfa() {
REP(i,1,n) f[i]=dep[i]=INF,vis[i]=0;
f[S]=dep[S]=f[T]=dep[T]=INF;
dep[S]=0,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
vis[u] = 0;
for (int i=head[u]; i; i=e[i].next) {
if (dep[e[i].to]>dep[u]+e[i].v&&e[i].w) {
dep[e[i].to]=dep[u]+e[i].v;
pre[e[i].to]=u,pre2[e[i].to]=i;
f[e[i].to]=min(f[u],e[i].w);
if (!vis[e[i].to]) {
vis[e[i].to]=1;
Q.push(e[i].to);
}
}
}
}
return dep[T]!=INF;
}
void EK(){
while(spfa()) {
int w = f[T];
for (int u=T; u!=S; u=pre[u]) {
e[pre2[u]].w-=w;
e[pre2[u]^1].w+=w;
}
flow += w, cost += w*dep[T];
}
}
void add(int u, int v, int w, int k) {
e[++cnt] = edge(v,w,k,head[u]);
head[u] = cnt;
e[++cnt] = edge(u,0,-k,head[v]);
head[v] = cnt;
}
费用流dinic+dijkstra板子
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <string.h>
#include <bitset>
#define REPP(i,a,b,d) for(int i=a; i<=b; i+=d)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,d) for(int i=a; i>=b; i-=d)
#define REV(i,a,b) REVV(i,a,b,1)
#define FOR(i,n) for(int i=0; i<n; i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int OO = 1e9;
// end of macro
const int N = 1e5+10;
int SRC, SINK, n, m;
struct edge{int to, flow, cap, cost;};
vector<edge>edges;
vi lse[N];
void addEdge(int a, int b, int cap, int cost){
lse[a].pb(edges.size());
edges.pb({b, 0, cap, cost});
lse[b].pb(edges.size());
edges.pb({a, 0, 0, -cost}); // here cap=0, cannot make 2 way, have to call this function twice, because of cost
}
int level[N]; // to prevent infinite loop during dfs
int potential[N];
int dist[N];
int lastEdge[N];
int ccost(int now, edge& e){ // compute cost w/ potentials
return e.cost + potential[now] - potential[e.to];
}
// almost like dinic's bfs, but dijkstra instead
bool dijkstra(){
REP(i,1,n) {
potential[i] += dist[i];
dist[i] = -1;
level[i] = 0;
}
priority_queue<pii>pq;
level[SRC] = 0;
pq.push(mp(0, SRC));
dist[SRC] = 0;
while(!pq.empty()){
int d = -pq.top().F;
int now = pq.top().S;
pq.pop();
if(dist[now] != d)continue;
FOR(i,lse[now].size()){
edge& e = edges[lse[now][i]];
if(e.flow < e.cap){
if(dist[e.to] != -1 && dist[e.to] <= d+ccost(now, e))continue;
dist[e.to] = d+ccost(now, e);
level[e.to] = max(level[e.to], level[now]+1);
pq.push(mp(-d-ccost(now, e), e.to));
}
}
}
return dist[SINK] != -1;
}
int dfs(int now, int flow){ // do the flow
if(now == SINK)return flow;
//printf("at %d, flow %d
",now,flow);
int ret = 0;
for(int& i = lastEdge[now]; i<lse[now].size(); i++){
edge& e = edges[lse[now][i]];
if(level[e.to] <= level[now])continue; //going back
if(e.flow == e.cap)continue; // no flow
if(dist[e.to] == dist[now] + ccost(now, e)){
//printf("%d -> %d
",now,e.to);
int curr = dfs(e.to, min(flow, e.cap - e.flow));
if(curr > 0){
e.flow += curr; // forward flow
edges[lse[now][i]^1].flow -= curr; // residual
flow -= curr;
ret += curr;
if(flow == 0)return ret; // if flow to this node is already depleted, i.e. there is a bottleneck far before this node
}
}
}
return ret;
}
int totalflow, totalcost;
void MCMF(){
totalflow = totalcost = 0;
while(dijkstra()) {
//printf("dist %d
",dist[SINK] + potential[SINK]);
//REP(i,1,n*m)printf("%d = %d
",i,dist[i]+potential[i]);
REP(i,1,n) lastEdge[i]=0;
lastEdge[SRC]=lastEdge[SINK]=0;
int flow = dfs(SRC, OO);
totalflow += flow;
totalcost += flow * (dist[SINK] + potential[SINK]);
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &SRC, &SINK);
REP(i,1,m) {
int u,v,w,f;
scanf("%d%d%d%d",&u,&v,&w,&f);
addEdge(u,v,w,f);
}
MCMF();
printf("%d %d
",totalflow,totalcost);
}