求救!63,2T,2W
查看原帖
求救!63,2T,2W
544756
xiaobing楼主2024/12/23 21:36
//#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lll __int128
#define ull unsigned long long
#define ui unsigned int
#define veci vector<int>
#define vecb vector<bool>
#define vecl vector<long long>
#define vecn vector<node>
#define vece vector<edge>
#define quei queue<int>
#define quen queue<node>
const int N = 3e5 + 10, inf = 0x5FFFFFFF;
const ll INF = 0x7FFFFFFFFFFFFFFF;
struct edge {
	int x, w, c, nxt;
};
edge e[N];
int n;
int head[N];
int tot = 1;
bool vis[N];
int in[N];
int cst[N];
int flw[N];
int cnt[N];
void insert(int u, int v, int w, int c) {
	e[++tot] = { v,w,c,head[u] };
	head[u] = tot;
	e[++tot] = { u,0,-c,head[v] };
	head[v] = tot;
}
bool spfa(int S, int T, int& flow, int& cost) {
	quei q;
	for (int i = 1; i <= n; i++)
		vis[i] = 0, cst[i] = inf;
	vis[S] = 1; in[S] = 0;
	cst[S] = 0; flw[S] = inf;
	cnt[S] = 1; q.push(S);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (u == T) {
			flow = flw[u];
			cost = cst[u];
			return 1;
		}
		vis[u] = 0;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].x;
			if (e[i].w && cst[u] + e[i].c < cst[v]) {
				in[v] = i ^ 1;
				cst[v] = cst[u] + e[i].c;
				flw[v] = min(flw[u], e[i].w);
				cnt[v] = cnt[u] + 1;
				if (cnt[v] > n)return 0;
				if (!vis[v])vis[v] = 1, q.push(v);
			}
		}
	}
	return 0;
}
void updata(int u, int flow) {
	int it = in[u];
	if (!it)return;
	e[it].w += flow;
	e[it ^ 1].w -= flow;
	updata(e[it].x, flow);
}
void EK(int S, int T, int& res1, int& res2) {
	int flow, cost;
	res1 = 0; res2 = 0;
	while (spfa(S, T, flow, cost)) {
		res1 += flow;
		res2 += flow * cost;
		updata(T, flow);
	}
	return;
}
signed main() {
	//freopen("train.in", "r", stdin);
	//freopen("train.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int m, s, t;
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= m; i++) {
		int u, v, w, c;
		cin >> u >> v >> w >> c;
		insert(u, v, w, c);
	}
	int res1, res2;
	EK(s, t, res1, res2);
	cout << res1 << ' ' << res2;
	return 0;
}
2024/12/23 21:36
加载中...