求条,54ptsTLE,EK + SPFA
查看原帖
求条,54ptsTLE,EK + SPFA
1192413
jimmy9_666楼主2024/11/30 20:29
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#define LL long long
#define int long long

using namespace std;

const int N = 5e3 + 10, M = 5e4 + 10;
const LL Inf = 1e18;

int n, m, s, t;
struct node {
	int v, nxt;
	LL w, f;
} e[M << 1];
int head[N], tot = 1;
LL maxf, minc;
int vis[N], pre[N], flow[N];
LL dis[N], incf[N];

void add(int u, int v, int w, int f) {
	e[++ tot].v = v, e[tot].w = w, e[tot].nxt = head[u], e[tot].f = f, head[u] = tot;
}

bool spfa() {
	for (int i = 1; i <= n; i ++ )
		vis[i] =  false, dis[i] = Inf;
	queue<int> q;
	q.push(s);
	vis[s] = true, dis[s] = 0, incf[s] = Inf;
	while (!q.empty()) {
		int u = q.front();
		vis[u] = false;
		q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			if (!e[i].w)
				continue;
			int v = e[i].v;
			if (dis[u] + e[i].f < dis[v]) {
				dis[v] = dis[u] + e[i].f;
				incf[v] = min(incf[u], e[i].w);
				pre[v] = i;
				if (!vis[v])
					vis[v] = true, q.push(v);
			}
		}
	}
	return dis[t] != Inf;
}

void MCMF() {
	while (spfa()) {
		int u = t;
		maxf += incf[t], minc += dis[t] * incf[t];
		while (u != s) 		
			e[pre[u]].w -= incf[t], e[pre[u] ^ 1].w += incf[t], u = e[pre[u] ^ 1].v;
	}
}

signed main() {
	scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
	for (int i = 1; i <= m; i ++ ) {
		int u, v, w, f;
		scanf("%lld%lld%lld%lld", &u, &v, &w, &f);
		add(u, v, w, f);
		add(u, v, 0, -f);
	}
	MCMF();
	printf("%lld %lld\n", maxf, minc);
	return 0;
}
2024/11/30 20:29
加载中...