题目大意：最小费用最大流
题解：最小费用最大流
卡点：1.太久不打MCMF，反向弧费用未取相反数
C++ Code：
#include#include #define maxn 5010#define maxm 50100using namespace std;const int inf = 0x3f3f3f3f;int n, m, S, T, MF;int q[maxm], h, t;int d[maxn], pre[maxn];bool vis[maxn];int head[maxn], cnt = 2;struct Edge { int to, nxt, w, cost;} e[maxm << 1];void add(int a, int b, int c, int d) { e[cnt] = (Edge) {b, head[a], c, d}; head[a] = cnt; e[cnt ^ 1] = (Edge) {a, head[b], 0, -d}; head[b] = cnt ^ 1; cnt += 2;}inline int min(int a, int b) {return a < b ? a : b;}bool spfa() { memset(d, 0x3f, sizeof d); d[q[h = t = 0] = S] = 0; while (h <= t) { int u = q[h++]; vis[u] = false; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (e[i].w && d[v] > d[u] + e[i].cost) { d[v] = d[u] + e[i].cost; pre[v] = i; if (!vis[v]) { q[++t] = v; vis[v] = true; } } } } return d[T] != inf;}int update() { int ans, mf = inf; for (int i = pre[T]; i; i = pre[e[i ^ 1].to]) mf = min(mf, e[i].w); ans = mf * d[T]; MF += mf; for (int i = pre[T]; i; i = pre[e[i ^ 1].to]) e[i].w -= mf, e[i ^ 1].w += mf; return ans;}void MCMF() { int ans = 0; while (spfa()) ans += update(); printf("%d %d\n", MF, ans);}int main() { scanf("%d%d%d%d", &n, &m, &S, &T); for (int i = 0; i < m; i++) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); add(a, b, c, d); } MCMF(); return 0;}