QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#333635 | #4269. Rainy Markets | Eric1230 | 0 | 14ms | 60584kb | C++14 | 2.5kb | 2024-02-20 10:52:26 | 2024-02-20 10:52:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 10, M = 4e6 + 10, inf = 1e9;
int n, m, B[N], P[N], U[N], tot = 1, head[N], dis[N], pre[N], inq[N];
int id[N][3];
struct Edge {int v, next, c, w;} e[M << 1];
void add(int u, int v, int c, int w) {e[++tot] = (Edge) {v, head[u], c, w}, head[u] = tot;}
void Add(int u, int v, int c, int w) {/*cout << u << ' ' << v << ' ' << c << ' ' << w << endl, */add(u, v, c, w), add(v, u, 0, -w);}
bool SPFA(int s, int t) {
memset(dis, 0x3f3f3f3f, sizeof dis);
memset(pre, 0, sizeof pre);
memset(inq, 0, sizeof inq);
queue <int> q;
dis[s] = 0, q.push(s), inq[s] = 1;
while(!q.empty()) {
int u = q.front();
inq[u] = 0, q.pop();
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].v, c = e[i].c, w = e[i].w;
if(c && dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pre[v] = i;
if(!inq[v]) q.push(v), inq[v] = 1;
}
}
}
return pre[t] > 0;
}
pair<int, int> EK(int s, int t) {
int mxflow = 0, mncost = 0;
while(SPFA(s, t)) {
int bottleneck = inf;
for(int i = pre[t]; i; i = pre[e[i ^ 1].v])
bottleneck = min(bottleneck, e[i].c);
mxflow += bottleneck;
for(int i = pre[t]; i; i = pre[e[i ^ 1].v]) {
e[i].c -= bottleneck;
e[i ^ 1].c += bottleneck;
mncost += e[i].w * bottleneck;
}
}
return make_pair(mxflow, mncost);
}
signed main() {
// freopen("test.in", "r", stdin);
ios :: sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> B[i];
for(int i = 1; i <= n - 1; i++) cin >> P[i];
for(int i = 1; i <= n - 1; i++) cin >> U[i];
int S = 2 * n + 1, T = 2 * n + 2;
for(int i = 1; i <= n - 1; i++) {
Add(i, i + n, inf, 0);
id[i][0] = tot;
Add(i, i + n + 1, inf, 0);
id[i][1] = tot;
Add(i, T, U[i], 1);
id[i][2] = tot;
// cout << U[i] << '\n';
}
for(int i = 1; i <= n - 1; i++) Add(S, i, P[i], 0);
for(int i = 1; i <= n; i++) Add(i + n, T, B[i], 0);
// cout << "------------------------------\n";
pair<int, int> ans = EK(S, T);
int sum = 0;
for(int i = 1; i <= n; i++) sum += P[i];
// cout << ans.first << ' ' << ans.second << endl;
if(ans.first != sum) return cout << "NO\n", 0;
cout << "YES\n" << ans.second << '\n';
for(int i = 1; i <= n - 1; i++) {
for(int j = 0; j < 3; j++) cout << e[id[i][j]].c << ' ';
cout << '\n';
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 12ms
memory: 60584kb
input:
3 10 15 10 20 20 0 0
output:
NO
result:
ok IMPOSSIBLE
Test #2:
score: -5
Wrong Answer
time: 3ms
memory: 58852kb
input:
2 813741488 132495829 946237313 0
output:
YES 0 813741484 132495829 0
result:
wrong answer the number of umbrellas for sale at market 1 is 0, but you used 132495829 umbrella(s)
Subtask #2:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 14ms
memory: 60420kb
input:
3 10 15 10 20 20 0 11
output:
YES 5 10 10 0 5 10 5
result:
wrong answer the number of umbrellas for sale at market 1 is 0, but you used 10 umbrella(s)
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%