• 最大流
  • 二分图最大匹配
• 费用流
  • 二分图最佳匹配

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10000 + 5;

int n, m, s, t;
struct Edge {
	int v, r, cp;
};
vector<Edge> g[maxn];
int cur[maxn];
int dis[maxn];

void add_edge(int u, int v, int c) {
	int i = g[u].size(), j = g[v].size();
	g[u].push_back(Edge{v, c, j});
	g[v].push_back(Edge{u, 0, i});
}

bool bfs() {
	queue<int> que;
	memset(dis, -1, sizeof(dis));
	dis[s] = 0, que.push(s);
	while (!que.empty()) {
		int u = que.front();
		que.pop();
		if (u == t) return true;
		for (const Edge &e: g[u]) if (e.r) {
			int v = e.v;
			if (dis[v] == -1) {
				dis[v] = dis[u] + 1, que.push(v);
			}
		}
	}
	return false;
}

int dfs(int u, int lim) {
	if (u == t) return lim;
	int flow = 0;
	for (int &i = cur[u]; i < g[u].size(); i++) {
		int v = g[u][i].v, r = g[u][i].r, j = g[u][i].cp;
		if (dis[u] + 1 != dis[v]) continue;
		int dlt = dfs(v, min(r, lim - flow));
		flow += dlt, g[u][i].r -= dlt, g[v][j].r += dlt;
		if (flow == lim) break;
	}
	return flow;
}

int main() {
	cin >> n >> m >> s >> t;
	while (m--) {
		int u, v, c;
		cin >> u >> v >> c;
		add_edge(u, v, c);
	}
	int flow = 0;
	while (bfs()) {
		memset(cur, 0, sizeof(cur));
		flow += dfs(s, 1e9);
	}
	cout << flow << '\n';
	
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5000 + 5;

int n, m, s, t;
struct Edge {
	int v, r, p, cp;
};
vector<Edge> g[maxn];
int dis[maxn];
bool inq[maxn];
int cur[maxn];

void add_edge(int u, int v, int w, int c) {
	g[u].push_back(Edge{v, w, c, g[v].size()});
	g[v].push_back(Edge{u, 0, -c, g[u].size() - 1});
}

bool spfa() {
	queue<int> que;
	memset(dis, 0x3f, sizeof(int) * (n + 1));
	memset(inq, false, sizeof(bool) * (n + 1));
	dis[s] = 0, inq[s] = true, que.push(s);
	while (!que.empty()) {
		int u = que.front();
		que.pop();
		inq[u] = false;
		for (const Edge &e: g[u]) if (e.r) {
			int v = e.v;
			if (dis[u] + e.p < dis[v]) {
				dis[v] = dis[u] + e.p;
				if (!inq[v]) inq[v] = true, que.push(v);
			}
		}
	}
	return dis[t] != dis[0];
}

bool vis[maxn];

int dfs(int u, int lim, int &cost) {
	if (u == t) return lim;
	vis[u] = true;
	int flow = 0;
	for (int &i = cur[u]; i < g[u].size(); i++) {
		int v = g[u][i].v, r = g[u][i].r, p = g[u][i].p, j = g[u][i].cp;
		if (dis[u] + p != dis[v] || !r || vis[v]) continue;
		int dlt = dfs(v, min(r, lim - flow), cost);
		flow += dlt, cost += dlt * p;
		g[u][i].r -= dlt, g[v][j].r += dlt;
		if (flow == lim) break;
	}
	vis[u] = false;
	return flow;
}

void dinic() {
	int flow = 0, cost = 0;
	while (spfa()) {
		memset(cur, 0, sizeof(int) * (n + 1));
		flow += dfs(s, 1e9, cost);
	}
	cout << flow << ' ' << cost << '\n';
}

int main() {
	cin >> n >> m >> s >> t;
	while (m--) {
		int u, v, w, c;
		cin >> u >> v >> w >> c;
		add_edge(u, v, w, c);
	}
	dinic();

	return 0;
}