#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
const int inf = 1e9;
ll n, m, r, k, t, p[2000], d[2000], u[2000], S, T;
vector < pair <int, int> > ans[2000];
struct edge {
ll x, to, cap, cost;
int twin;
};
edge* pr[N];
vector <edge> g[N];
ll find_path () {
fill (d, d + T + 1, INF);
fill (u, u + T + 1, 0);
d[S] = 0;
for (ll st = 0; st <= T; st++) {
ll x = -1;
for (ll i = 0; i <= T; i++) {
if (!u[i] && (x == -1 || d[x] > d[i])) x = i;
}
u[x] = 1;
if (d[x] == INF) continue;
for (auto& e : g[x])
if (e.cap && d[e.to] > d[e.x] - p[e.to] + p[e.x] + e.cost) {
d[e.to] = d[e.x] - p[e.to] + p[e.x] + e.cost;
pr[e.to] = &e;
}
}
for (ll i = 0; i <= T; i++){
p[i] += d[i];
}
if (!u[T] || d[T] == INF) return -INF;
ll x = T;
ll mn = INF, cost = 0;
while (x != S) {
mn = min (mn, pr[x] -> cap);
x = pr[x] -> x;
}
x = T;
while (x != S) {
pr[x] -> cap -= mn;
g[pr[x] -> to][pr[x] -> twin].cap += mn;
cost = pr[x] -> cost * mn;
x = pr[x] -> x;
}
return cost;
}
ll mcmf () {
ll a = 0, s = 0;
while ((a = find_path ()) != -INF) {
s += a;
}
return s;
}
void add (ll x, ll to, ll cost) {
edge u, v;
u = {x, to, 1, cost, 0};
v = {to, x, 0, -cost, 0};
g[x].push_back (u);
g[to].push_back (v);
g[x][g[x].size () - 1].twin = g[to].size () - 1;
g[to][g[to].size () - 1].twin = g[x].size () - 1;
}
int main () {
cin >> n >> m >> r >> t >> k;
for (ll i = 1; i <= n; i++) {
for (ll j = 0; j < min (m, t / r); j++)
add (0, i, j + 1);
}
T = n + m + 1;
for (ll i = n + 1; i <= n + m; i++) {
add (i, T, 0);
}
for (ll i = 0; i < k; i++) {
ll a, b;
cin >> a >> b;
add (a, n + b, 0);
}
int s = 0, f = mcmf () * r;
for (int i = 1; i <= n; i++) {
int t = 0;
for (edge e : g[i]) {
if (!e.cap && e.to) {
ans[i].push_back ({e.to - n, t});
s++;
t += r;
}
}
}
cout << s << ' ' << f << endl;
for (int i = 1; i <= n; i++) {
for (auto a : ans[i])
cout << i << ' ' << a.first << ' ' << a.second << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
24056 KB |
Output is correct |
2 |
Correct |
23 ms |
24056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
24056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
24184 KB |
Output is correct |
2 |
Correct |
20 ms |
23928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
114 ms |
26232 KB |
Output is correct |
2 |
Correct |
115 ms |
26328 KB |
Output is correct |
3 |
Correct |
34 ms |
23928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1071 ms |
34396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1086 ms |
34912 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1088 ms |
34552 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
923 ms |
26360 KB |
Output is correct |
2 |
Runtime error |
78 ms |
35192 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1089 ms |
56432 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1094 ms |
27256 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |