QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#706583	#561. 税收	TheZone	100 ✓	213ms	4408kb	C++20	3.2kb	2024-11-03 12:24:50	2024-11-03 12:24:56

Judging History

This is the latest submission verdict.

[2024-11-03 12:24:56]
Judged

Verdict: 100
Time: 213ms
Memory: 4408kb

Show

[2024-11-03 12:24:50]
Submitted

answer

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
const int N = 205, M = 20005 << 1;
 
int n, m, p, s, t;
 
int top, head[N], to[M], nxt[M], c[M], l[M];
 
void addedge(int u, int v, int cap, int len) {
	to[top] = v, nxt[top] = head[u], c[top] = cap, l[top] = len, head[u] = top++;
}
 
vector<pair<int, int> > paths;
 
int dis[N], fa[N];
 
bool inque[N];
 
const int INF = 1000000000;
 
bool go(int source, int target) {
	for (int i = 0; i < n; ++i) {
		dis[i] = INF;
	}
	dis[source] = 0;
	inque[source] = true;
	queue<int> q;
	q.push(source);
	while (q.size()) {
		int u = q.front();
		inque[u] = false;
		q.pop();
		for (int i = head[u]; ~i; i = nxt[i]) {
			if (c[i]) {
				int v = to[i], nd = dis[u] + l[i];
				if (dis[v] > nd) {
					dis[v] = nd;
					fa[v] = i;
					if (!inque[v]) {
						inque[v] = true;
						q.push(v);
					}
				}
			}
		}
	}
	if (dis[target] == INF) {
		return false;
	}
	int f = INF;
	int u = target;
	while (u != source) {
		int e = fa[u];
		f = min(f, c[e]);
		u = to[e ^ 1];
	}
	paths.push_back(make_pair(f, dis[target]));
	u = target;
	while (u != source) {
		int e = fa[u];
		c[e] -= f, c[e ^ 1] += f;
		u = to[e ^ 1];
	}
	return true;
}
 
int main() { 
	scanf("%d%d%d%d%d", &n, &m, &p, &s, &t);
	--s, --t;
	top = 0;
	memset(head, -1, sizeof(head));
	for (int i = 0; i < m; ++i) {
		int u, v, d, c;
		scanf("%d%d%d%d", &u, &v, &d, &c);
		--u, --v;
		addedge(u, v, c, d);
		addedge(v, u, 0, -d);
	}
	while (go(s, t)) {
		continue;
	}
	int csum = 0, fsum = 0;
	for (int i = 0; i < (int)paths.size(); ++i) {
		csum += paths[i].first * paths[i].second;
		fsum += paths[i].first;
		double ans = (double)(p + csum) / fsum;
		if (i + 1 == paths.size() || ans < paths[i + 1].second) {
			printf("%.4f\n", ans);
			return 0;
		}
	}
	return 0;
}
/*#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
const int N = 205, M = 20005 << 1;
 
int n, m, p, s, t;
 
int top, head[N], to[M], nxt[M], c[M], l[M];
 
void addedge(int u, int v, int cap, int len) {
	to[top] = v, nxt[top] = head[u], c[top] = cap, l[top] = len, head[u] = top++;
}
 
vector<pair<int, int> > paths;
 
int dis[N], fa[N];
 
bool inque[N];
 
const int INF = 1000000000;
 
bool go(int source, int target) {
	for (int i = 0; i < n; ++i) {
		dis[i] = INF;
	}
	dis[source] = 0;
	inque[source] = true;
	queue<int> q;
	q.push(source);
	while (q.size()) {
		int u = q.front();
		inque[u] = false;
		q.pop();
		for (int i = head[u]; ~i; i = nxt[i]) {
			if (c[i]) {
				int v = to[i], nd = dis[u] + l[i];
				if (dis[v] > nd) {
					dis[v] = nd;
					fa[v] = i;
					if (!inque[v]) {
						inque[v] = true;
						q.push(v);
					}
				}
			}
		}
	}
	if (dis[target] == INF) {
		return false;
	}
	int f = INF;
	int u = target;
	while (u != source) {
		int e = fa[u];
		f = min(f, c[e]);
		u = to[e ^ 1];
	}
	paths.push_back(make_pair(f, dis[target]));
	u = target;
	while (u != source) {
		int e = fa[u];
		c[e] -= f, c[e ^ 1] += f;
		u = to[e ^ 1];
	}
	return true;
}
	}
	return 0;
}
*/

源文件, 语言: C++20

詳細信息

Pretests

Final Tests

Test #1:

score: 10

Accepted

time: 0ms

memory: 3868kb

input:

100 99 10000 1 100
1 2 3 6
2 3 8 1
3 4 1 5
4 5 9 1
5 6 5 5
6 7 5 4
7 8 8 7
8 9 2 1
9 10 7 5
10 11 5 1
11 12 8 8
12 13 3 8
13 14 1 7
14 15 5 6
15 16 1 8
16 17 6 8
17 18 2 4
18 19 10 4
19 20 4 2
20 21 6 9
21 22 5 7
22 23 10 2
23 24 4 9
24 25 1 10
25 26 6 10
26 27 7 6
27 28 9 6
28 29 8 5
29 30 7 9
30 3...

output:

10497.0000

result:

ok found '10497.00000', expected '10497.00000', error '0.00000'

Test #2:

score: 10

Accepted

time: 0ms

memory: 3812kb

input:

30 100 10 1 30
1 2 1 1
2 3 5 1
3 4 4 1
4 5 2 1
5 6 10 1
6 7 1 1
7 30 2 1
23 26 4 1
11 5 5 1
26 25 6 1
26 21 5 1
11 6 6 1
27 12 4 1
14 27 1 1
17 26 2 1
21 29 4 1
27 29 2 1
14 19 8 1
29 21 9 1
28 2 6 1
18 12 5 1
27 12 3 1
14 13 10 1
4 6 9 1
23 11 10 1
4 22 2 1
23 24 1 1
23 1 5 1
5 10 6 1
17 27 5 1
8 9...

output:

21.0000

result:

ok found '21.00000', expected '21.00000', error '0.00000'

Test #3:

score: 10

Accepted

time: 0ms

memory: 3916kb

input:

50 150 60 1 50
1 2 5 1
2 3 8 1
3 50 2 1
11 24 8 1
3 50 8 1
28 24 7 1
14 3 7 1
37 23 7 1
13 15 7 1
42 27 8 1
50 3 2 1
29 31 5 1
4 23 9 1
33 20 8 1
38 13 3 1
43 3 10 1
4 17 5 1
17 1 5 1
10 35 8 1
45 17 9 1
31 10 5 1
26 25 2 1
31 4 2 1
9 37 4 1
44 50 6 1
49 5 2 1
3 28 4 1
27 23 6 1
32 29 4 1
45 27 8 1
...

output:

37.2500

result:

ok found '37.25000', expected '37.25000', error '0.00000'

Test #4:

score: 10

Accepted

time: 0ms

memory: 3792kb

input:

50 200 72 1 50
1 2 4 1
2 3 4 1
3 4 5 1
4 5 10 1
5 6 3 1
6 7 8 1
7 8 9 1
8 9 9 1
9 10 7 1
10 50 7 1
17 16 10 1
26 45 8 1
21 41 6 1
2 12 9 1
32 40 9 1
28 7 8 1
2 13 7 1
1 13 1 1
11 50 10 1
33 20 10 1
14 17 3 1
43 25 4 1
31 47 5 1
48 27 4 1
42 12 6 1
41 23 2 1
27 36 2 1
5 19 4 1
13 38 6 1
50 41 5 1
6 4...

output:

33.4000

result:

ok found '33.40000', expected '33.40000', error '0.00000'

Test #5:

score: 10

Accepted

time: 1ms

memory: 3896kb

input:

100 400 300 1 100
1 2 3 5
2 3 10 3
3 4 2 7
4 5 2 1
5 6 8 4
6 7 10 3
7 8 5 9
8 9 10 8
9 10 1 8
10 11 10 5
11 12 6 10
12 13 10 5
13 14 9 2
14 15 10 2
15 16 4 7
16 17 8 6
17 18 5 1
18 19 9 2
19 20 4 4
20 100 3 6
3 7 8 10
18 20 8 8
70 93 1 8
51 87 10 3
47 41 7 6
54 13 4 7
19 37 1 8
50 72 9 3
61 82 5 7
8...

output:

29.6800

result:

ok found '29.68000', expected '29.68000', error '0.00000'

Test #6:

score: 10

Accepted

time: 44ms

memory: 4108kb

input:

200 10000 1000000 1 200
36 46 7 5
157 114 10 1
75 158 2 4
73 11 2 6
95 46 1 4
22 105 8 2
13 172 10 6
187 135 10 8
114 136 9 10
155 5 9 8
189 173 10 5
85 126 8 10
124 92 2 5
94 74 1 4
127 193 6 3
23 37 4 2
18 172 1 9
153 66 9 7
129 78 7 2
128 81 5 5
188 71 5 6
198 35 10 5
68 103 9 4
79 117 3 7
87 98 ...

output:

4707.4272

result:

ok found '4707.42720', expected '4707.42723', error '0.00000'

Test #7:

score: 10

Accepted

time: 15ms

memory: 3976kb

input:

100 5000 100 1 100
43 95 5 1
40 86 1 5
51 20 10 7
65 53 8 3
75 47 5 3
27 14 6 8
58 95 3 8
23 48 6 9
3 73 4 2
7 40 6 3
98 71 10 9
71 28 8 2
49 19 2 5
18 15 1 1
42 46 8 9
56 54 2 8
25 16 4 9
99 48 4 3
44 50 4 1
17 63 3 7
65 75 8 9
30 43 2 7
54 82 7 2
52 72 3 2
88 82 6 1
89 80 3 2
8 75 4 3
31 20 10 9
1...

output:

6.4143

result:

ok found '6.41430', expected '6.41429', error '0.00000'

Test #8:

score: 10

Accepted

time: 213ms

memory: 4404kb

input:

150 20000 2048 1 150
50 44 6 7
20 8 9 9
74 32 5 7
110 45 1 10
52 104 5 7
128 46 8 6
36 91 9 4
19 58 8 8
38 20 8 6
16 9 4 2
73 123 8 7
8 66 6 9
12 59 1 3
10 112 4 3
28 141 2 9
23 122 5 3
126 131 7 3
115 32 4 6
49 110 8 5
60 103 9 1
71 59 10 4
138 128 4 1
76 55 8 10
142 134 8 7
69 125 5 10
67 139 10 4...

output:

12.1576

result:

ok found '12.15760', expected '12.15762', error '0.00000'

Test #9:

score: 10

Accepted

time: 85ms

memory: 4408kb

input:

200 15000 1000 1 200
57 146 4 3
53 130 10 3
150 144 3 10
55 137 7 7
182 33 7 10
84 118 8 5
199 77 10 3
188 46 7 8
3 137 1 6
198 111 5 4
90 48 7 10
46 161 10 10
59 116 4 7
18 59 4 1
52 40 5 2
48 141 9 5
80 84 5 3
96 65 8 7
187 176 2 3
176 89 1 9
39 106 4 3
55 126 8 6
80 56 1 8
147 69 7 9
188 15 2 1
2...

output:

12.6869

result:

ok found '12.68690', expected '12.68687', error '0.00000'

Test #10:

score: 10

Accepted

time: 168ms

memory: 4404kb

input:

200 20000 1000000 1 200
64 195 5 6
183 2 1 7
26 6 8 10
100 179 10 4
62 162 9 10
187 40 8 7
112 10 8 2
4 134 3 8
115 4 4 9
177 60 9 6
10 73 3 6
131 106 1 8
53 73 10 8
79 3 4 2
129 189 8 5
123 7 3 4
34 90 3 10
77 198 9 5
22 142 9 8
192 25 10 4
107 200 8 2
125 121 5 4
84 154 4 9
5 151 6 4
104 105 6 9
1...

output:

1882.9757

result:

ok found '1882.97570', expected '1882.97566', error '0.00000'