1 .Edmonds-Karp 算法 ： 通过反向增光路+bfs 求解最大流
#includeusing namespace std;#define LOACL freopen("in","r",stdin);\ freopen("out","w",stdout);#define FASTIO ios::sync_with_stdio(false);#define CLOCK cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";#define add(u,v,w) e[++tot]=(edge){v,head[u],1},head[u]=tot;#define CLR(arr,val) memset(arr,val,sizeof(arr))#define DBG(x) cout<<(#x)<<"="< <
2Dinic 算法 BFS 分层 DFS 找最大流
#includeusing namespace std;#define LOACL freopen("in","r",stdin);\ freopen("out","w",stdout); #define FASTIO ios::sync_with_stdio(false);#define CLOCK cout<<1.*clock()/CLOCKS_PER_SEC<<"ms"<<"\n";const int inf = 987654321;const int sz = (int)100010;const int mod = (int)1e9 + 7;const int sqrtn = 300; #define add(u,v,w) e[++tot]=(edge){v,head[u],w},head[u]=tot; #define CLR(arr,val) memset(arr,val,sizeof(arr)) #define DBG(x) cout<<(#x)<<"="< <
费用流 EK算法 spfa 找增广路 + 尾部合并
#includeusing namespace std;#define LOACL freopen("in","r",stdin);\ freopen("out","w",stdout);const int sz = 50010;const int inf = 0x3f3f3f3f;#define CLR(arr,val) memset(arr,val,sizeof(arr))#define REP(i, a, b) for(int i=(a); i<=(b); i++)#define Loop(i,u) for(int i = head[u];i!=-1;i=e[i].nxt)int n, m, s, t, u, v, w, f;struct edge{ int v, nxt, w, f;} e[sz << 1];int tot = -1, head[sz], pre[sz], inq[sz], dist[sz], incf[sz], maxflow, ans;void add(int u, int v, int w, int f){ e[++tot] = (edge) {v, head[u], w, f}, head[u] = tot;} bool spfa(int s, int t){ fill(dist, dist + n + 1, INT_MAX); CLR(inq, 0); queue q ; q.push(s); inq[s] = 1; dist[s] = 0; incf[s] = inf; while(!q.empty()) { int v = q.front();q.pop(); inq[v]=0; Loop(i,v) { if(e[i].w>0 && dist[e[i].v]>dist[v]+e[i].f) { dist[e[i].v]=dist[v]+e[i].f; incf[e[i].v]=min(e[i].w,incf[v]); pre[e[i].v]=i; if(!inq[e[i].v]) { q.push(e[i].v); inq[e[i].v]=1; } } } } return dist[t]!=INT_MAX;}void update(int s, int t){ int x = t; while (x != s) { int i = pre[x]; e[i].w -= incf[t]; e[i ^ 1].w += incf[t]; x = e[i ^ 1].v; } maxflow += incf[t]; ans += dist[t] * incf[t];}void EK(int s, int t){ while (spfa(s, t)) update(s, t);} int main(){ LOACL CLR(head,-1); cin >> n >> m >> s >> t; REP(i, 1, m) { cin >> u >> v >> w >> f; add(u, v, w, f); add(v, u, 0, -f); } EK(s, t); cout << maxflow << " " << ans << endl;}