RT

不会写 EK

#include <bits/stdc++.h>

using namespace std;

namespace Basic {
	template <typename Temp> inline void read(Temp & res) {
		Temp fh = 1; res = 0; char ch = getchar();
		for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = 1;
		for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
		res = res * fh;
	}
	template <typename Temp> inline void Checkmax(Temp num, Temp comp) {if(comp > num) num = comp;}
	template <typename Temp> inline void Checkmin(Temp num, Temp comp) {if(comp > num) num = comp;}
}

using namespace Basic;
const int Maxn = 5e3 + 5;
const int Maxm = 1e5 + 5;

int n, m, st, ed, x, y;
int z, h;

struct e {
	int to, nxt;
	int fl, cost;
} b[Maxm];
int head[Maxn], curr[Maxn], ecnt = 1;
int dis[Maxn];

void add(int u, int v, int w, int c) {b[++ecnt] = (e){v, head[u], w, c}; head[u] = ecnt;}

bool vis[Maxn];
queue <int> q;
bool spfa() {
	bool bl = 0;
	memset(dis, 127, sizeof(dis));
	while(!q.empty()) q.pop();
	q.push(st); vis[st] = 1; dis[st] = 0;
	while(!q.empty()) {
		int tnow = q.front(); q.pop(); vis[tnow] = 0;
		for(int i = head[tnow]; i; i = b[i].nxt) {
			int tto = b[i].to, tw = b[i].fl, tc = b[i].cost;
			if(!tw) continue; 
			if(dis[tnow] + tc < dis[tto]) {
				dis[tto] = dis[tnow] + tc;
				if(tto == ed) bl = 1;
				if(!vis[tto]) {
					q.push(tto);
					vis[tto] = 1;
				}
			}
		}
	}
	return bl;
}
int mincost, maxflow;
int dfs(int t, int flow) {
	if(t == ed) return flow;
	int rest = flow;
	for(int & i = curr[t]; i; i = b[i].nxt) {
		int tto = b[i].to, tw = b[i].fl, tc = b[i].cost;
		if(dis[t] + tc == dis[tto] && tw && (!vis[tto])) {
			int k = dfs(tto, min(rest, tw));
			if(!k) dis[tto] = -0x7fffffff;
			mincost += k * b[i].cost; rest -= k, b[i].fl -= k, b[i ^ 1].fl += k;
			if(!rest) break;
		}
	}
	return flow - rest;
}

signed main() {
	read(n); read(m); read(st); read(ed);
	while(m--) {
		read(x); read(y); read(z); read(h);
		add(x, y, z, h); add(y, x, 0, -h);
	}
	while(spfa()) {
		memcpy(curr, head, sizeof(curr));
		int now = 0;
		 while((now = dfs(st, 0x7fffffff))) maxflow += now;
	}
	printf("%d %d", maxflow, mincost);
	return 0;
}