QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#477766#602. 最小费用最大流(随机数据)NOI_AK_ME#0 0ms0kbC++203.5kb2024-07-14 10:07:062024-07-14 10:07:07

Judging History

This is the latest submission verdict.

  • [2024-07-14 10:07:07]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2024-07-14 10:07:06]
  • Submitted

answer

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
typedef long long i64;
i64 rd()
{
	i64 k = 0, f = 1;
	char s = getchar();
	while (s < '0' || s > '9')
	{
		if (s == '-')
			f = 0;
		s = getchar();
	}
	while (s >= '0' && s <= '9')
	{
		k = (k << 1) + (k << 3) + (s ^ '0');
		s = getchar();
	}
	return f ? k : -k;
}
void wr(i64 x)
{
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		wr(x / 10);
	putchar((x % 10) ^ '0');
}
// 1-indexed
namespace MCMF
{
	using cap = i64;

	const int N = 505;
	const int M = 15005;

	const i64 flow_INF = 1145141919810114514ll;
	const i64 cost_offset = 1145141919;

	int n, m, s, t;

	struct edge
	{
		int to, nxt;
		cap flow, cost;
	} e[M << 1];
	int cnt;
	int h[N];
	void init_sz(int _n) { n = _n, m = 0, cnt = 1; }
	int add_edge(int u, int v, cap flow, cap cost, bool directed = true)
	{
		++m;
		e[++cnt].to = v, e[cnt].nxt = h[u], e[cnt].flow = flow, e[cnt].cost = cost;
		h[u] = cnt;
		e[++cnt].to = u, e[cnt].nxt = h[v], e[cnt].flow = directed ? 0 : flow, e[cnt].cost = -cost;
		h[v] = cnt;
		return cnt;
	}
	int tme;
	int vis[N], fa[N], fae[N];
	void dfs(int u)
	{
		vis[u] = 1;
		for (int i = h[u], v; i; i = e[i].nxt)
			if (!vis[v = e[i].to] && e[i].flow)
				fa[v] = u, fae[v] = i, dfs(v);
	}

	int pi[N];
	int phi(int x)
	{
		if (vis[x] == tme)
			return pi[x];
		vis[x] = tme;
		return pi[x] = phi(fa[x]) - e[fae[x]].cost;
	}


	int cyc[N];

	i64 cost;

	void clr()
	{
		memset(h, 0, sizeof(h));
		tme = 0;
		memset(vis, 0, sizeof(vis)), memset(fa, 0, sizeof(fa)), memset(fae, 0, sizeof(fae));
		memset(pi, 0, sizeof(pi)), memset(cyc, 0, sizeof(cyc));
	}

	void pushflow(int id)
	{
		int pen = e[id ^ 1].to, lca = e[id].to;
		++tme;

		while (pen)
			vis[pen] = tme, pen = fa[pen];

		while (vis[lca] != tme)
			vis[lca] = tme, lca = fa[lca];

		int e2 = 0, f = e[id].flow, path = 2, clen = 0;

		for (int i = e[id ^ 1].to; i != lca; i = fa[i])
		{
			cyc[++clen] = fae[i];
			if (e[fae[i]].flow < f)
				f = e[fae[e2 = i] ^ (path = 0)].flow;
		}

		for (int i = e[id].to; i != lca; i = fa[i])
		{
			cyc[++clen] = fae[i] ^ 1;
			if (e[fae[i] ^ 1].flow < f)
				f = e[fae[e2 = i] ^ (path = 1)].flow;
		}

		cyc[++clen] = id;

		for (int i = 1; i <= clen; ++i)
		{
			e[cyc[i]].flow -= f, e[cyc[i] ^ 1].flow += f;
			cost += 1ll * f * e[cyc[i]].cost;
		}

		if (path == 2)
			return;

		int lste = id ^ path, lst = e[lste].to, now = e[lste ^ 1].to;

		while (lst != e2)
		{
			vis[now]--, lste ^= 1;
			std::swap(lste, fae[now]);
			std::swap(lst, fa[now]);
			std::swap(lst, now);
		}
	}

	std::pair<cap, cap> solve(int _s, int _t)
	{
		s = _s, t = _t;
		int lhead = h[s], rhead = h[t];
		add_edge(t, s, flow_INF, -cost_offset);
		dfs(t);
		vis[t] = tme = 2, fa[t] = cost = 0;

		for (int i = 2, pre = cnt; i != pre; i = (i == cnt ? 2 : i + 1))
			if (e[i].flow && e[i].cost < phi(e[i ^ 1].to) - phi(e[i].to))
				pushflow(pre = i);

		h[s] = lhead, h[t] = rhead;
		cnt -= 2; // extra operation if calculate minimum flow or other.
		return std::make_pair(e[cnt + 2].flow, cost + 1ll * e[cnt + 2].flow * cost_offset);
	}
}
int main()
{
	int n = rd(), m = rd(), s = rd(), t = rd();
	MCMF::init_sz(n);
	while (m--)
	{
		int u = rd(), v = rd(), flow = rd(), cost = rd();
		MCMF::add_edge(u, v, flow, cost);
	}
	std::pair<i64, i64> ans = MCMF::solve(s, t);
	wr(ans.first), putchar(' '), wr(ans.second);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

8 27
2 3 2147483647 100
1 3 1 100
2 4 2147483647 10
1 4 1 10
2 4 2147483647 10
1 4 1 10
2 8 3 0
3 5 2147483647 100
1 5 1 100
3 8 1 0
3 2 2147483647 0
4 5 2147483647 10
1 5 1 10
4 8 1 0
4 2 2147483647 0
5 6 2147483647 1
1 6 1 1
5 6 2147483647 1
1 6 1 1
5 7 2147483647 1
1 7 1 1
5 8 3 0
5 2 2147483647 ...

output:


result:


Test #2:

score: 0
Runtime Error

input:

12 49
2 10 2147483647 5
1 10 1 5
2 5 2147483647 50
1 5 1 50
2 9 2147483647 8
1 9 1 8
2 8 2147483647 47
1 8 1 47
2 11 2147483647 17
1 11 1 17
2 12 5 0
3 12 0 0
3 2 2147483647 0
4 6 2147483647 18
1 6 1 18
4 11 2147483647 12
1 11 1 12
4 9 2147483647 14
1 9 1 14
4 12 3 0
4 2 2147483647 0
5 11 2147483647...

output:


result:


Test #3:

score: 0
Runtime Error

input:

27 169
2 15 2147483647 24
1 15 1 24
2 19 2147483647 96
1 19 1 96
2 12 2147483647 49
1 12 1 49
2 13 2147483647 75
1 13 1 75
2 24 2147483647 2
1 24 1 2
2 27 5 0
3 27 0 0
3 2 2147483647 0
4 11 2147483647 99
1 11 1 99
4 3 2147483647 85
1 3 1 85
4 27 2 0
4 2 2147483647 0
5 27 0 0
5 2 2147483647 0
6 9 214...

output:


result:


Test #4:

score: 0
Runtime Error

input:

77 2149
2 42 2147483647 33
1 42 1 33
2 68 2147483647 30
1 68 1 30
2 76 2147483647 13
1 76 1 13
2 51 2147483647 93
1 51 1 93
2 12 2147483647 39
1 12 1 39
2 57 2147483647 74
1 57 1 74
2 70 2147483647 21
1 70 1 21
2 73 2147483647 24
1 73 1 24
2 52 2147483647 54
1 52 1 54
2 15 2147483647 99
1 15 1 99
2 ...

output:


result:


Test #5:

score: 0
Runtime Error

input:

102 4199
2 48 2147483647 42
1 48 1 42
2 85 2147483647 50
1 85 1 50
2 22 2147483647 83
1 22 1 83
2 95 2147483647 97
1 95 1 97
2 82 2147483647 34
1 82 1 34
2 25 2147483647 72
1 25 1 72
2 4 2147483647 17
1 4 1 17
2 47 2147483647 10
1 47 1 10
2 71 2147483647 12
1 71 1 12
2 68 2147483647 39
1 68 1 39
2 2...

output:


result:


Test #6:

score: 0
Runtime Error

input:

102 4199
2 79 2147483647 13
1 79 1 13
2 83 2147483647 73
1 83 1 73
2 75 2147483647 90
1 75 1 90
2 30 2147483647 92
1 30 1 92
2 54 2147483647 25
1 54 1 25
2 66 2147483647 53
1 66 1 53
2 52 2147483647 37
1 52 1 37
2 63 2147483647 46
1 63 1 46
2 11 2147483647 20
1 11 1 20
2 55 2147483647 53
1 55 1 53
2...

output:


result:


Test #7:

score: 0
Runtime Error

input:

102 4199
2 39 2147483647 45
1 39 1 45
2 51 2147483647 11
1 51 1 11
2 86 2147483647 63
1 86 1 63
2 23 2147483647 46
1 23 1 46
2 48 2147483647 63
1 48 1 63
2 87 2147483647 8
1 87 1 8
2 73 2147483647 63
1 73 1 63
2 5 2147483647 52
1 5 1 52
2 80 2147483647 21
1 80 1 21
2 31 2147483647 44
1 31 1 44
2 101...

output:


result:


Test #8:

score: 0
Runtime Error

input:

302 10599
2 72 2147483647 169
1 72 1 169
2 260 2147483647 165
1 260 1 165
2 12 2147483647 108
1 12 1 108
2 16 2147483647 26
1 16 1 26
2 28 2147483647 148
1 28 1 148
2 7 2147483647 74
1 7 1 74
2 139 2147483647 199
1 139 1 199
2 231 2147483647 9
1 231 1 9
2 287 2147483647 123
1 287 1 123
2 135 2147483...

output:


result:


Test #9:

score: 0
Runtime Error

input:

302 10599
2 222 2147483647 132
1 222 1 132
2 17 2147483647 7
1 17 1 7
2 177 2147483647 253
1 177 1 253
2 90 2147483647 195
1 90 1 195
2 128 2147483647 289
1 128 1 289
2 42 2147483647 193
1 42 1 193
2 213 2147483647 133
1 213 1 133
2 263 2147483647 293
1 263 1 293
2 50 2147483647 155
1 50 1 155
2 228...

output:


result:


Test #10:

score: 0
Runtime Error

input:

302 10599
2 176 2147483647 289
1 176 1 289
2 190 2147483647 99
1 190 1 99
2 10 2147483647 96
1 10 1 96
2 240 2147483647 165
1 240 1 165
2 273 2147483647 205
1 273 1 205
2 248 2147483647 194
1 248 1 194
2 220 2147483647 122
1 220 1 122
2 194 2147483647 167
1 194 1 167
2 8 2147483647 67
1 8 1 67
2 227...

output:


result: