QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#342670#602. 最小费用最大流(随机数据)_ZMF_#0 0ms0kbC++112.5kb2024-03-01 14:43:282024-03-01 14:43:29

Judging History

你现在查看的是最新测评结果

  • [2024-03-01 14:43:29]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-03-01 14:43:28]
  • 提交

answer

/*
    长弓背负,仙女月鹫,
	梦中徐来,长夜悠悠。
	今宵共君,夜赏囃子,
	盼君速归,长夜悠悠。
	睡意袭我,眼阖梦徭,
	睡意袭我,意归襁褓。
	手扶卓揭,仙女水狃,
	盼君速归,长夜悠悠。
	今宵共君,戏于西楼,
	盼君速归,长夜悠悠。
	睡意袭我,涟锜池留,
	睡意袭我,意归海角。
					                  ——《ever17》
*/
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int sum = 0, nega = 1;
	char ch = getchar();
	while (ch > '9'||ch < '0')
	{
	    if (ch == '-') nega = -1;
		ch = getchar();
	}
	while (ch <= '9'&&ch >= '0') sum = sum * 10 + ch - '0', ch = getchar ();
	return sum * nega;
}
const int N = 5009, M = 50009, INF = 1e18;
struct Dinic
{
	int n, m, s, t, cnt = 1;
	int to[M << 1], nxt[M << 1], val[M << 1], head[N], cost[M << 1];
	int a[N], ans, dis[N], vis[N];
	inline void addedge(int u, int v, int w, int c)
	{
		to[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt; cost[cnt] = c, val[cnt] = w;
		to[++cnt] = u, nxt[cnt] = head[v], head[v] = cnt; cost[cnt] = -c, val[cnt] = 0;
	}
	inline int spfa()
	{
		queue<int> q;
		for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0;
		dis[s] = 0, q.push(s); vis[s] = 1;
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			vis[u] = 0;
			for (int i = head[u]; i; i = nxt[i])
				if(val[i] && dis[to[i]] > dis[u] + cost[i])
				{
					dis[to[i]] = dis[u] + cost[i];
					if(!vis[to[i]])
					{
						vis[to[i]] = 1; q.push(to[i]);
					}
				}
		}
		return dis[t] != INF;
	}
	int ret;
	inline int dfs(int u, int flow)
	{
		if(u == t) return flow;
		vis[u] = 1;
		int res = flow, tot = 0;
		for (int i = head[u]; i; i = nxt[i])
			if(!vis[to[i]] && val[i] && dis[to[i]] == dis[u] + cost[i])
			{
				int pp = dfs(to[i], min(res, val[i]));
				res -= pp, val[i] -= pp, val[(i ^ 1)] += pp, tot += pp;
				ret += pp * cost[i];
			}
		vis[u] = 0;
		return tot;
	}
	inline void dinic()
	{
		while(spfa()) 
		{
			for (int i = 1; i <= n; i++) vis[i] = 0;
			ans += dfs(s, INF);
		}
		cout << ans << " " << ret << endl;
	}
}D;
signed main()
{
	D.n = read(), D.m = read(), D.s = read(), D.t = read();
	for (int i = 1; i <= D.m; i++)
	{
		int u = read(), v = read(), w = read(), c = read();
		D.addedge(u, v, w, c);
	}
	D.dinic();
	return 0;
}

详细

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: