QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#800165 | #1825. The King's Guards | ucup-team2172# | WA | 0ms | 4000kb | C++23 | 4.8kb | 2024-12-05 22:45:13 | 2024-12-05 22:45:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define sz(a) (int)(a).size()
using vi = vector<int>;
template<class Cap, class Cost, Cap Cap_MAX =
numeric_limits<Cap>::max(), Cost Cost_MAX =
numeric_limits<Cost>::max() / 4>
struct SuccessiveShortestPath{
int n;
struct E { int to; Cap a; Cost w; } ;
vector<E> es;
vector<vi> g;
vector<Cost> h;
SuccessiveShortestPath(int n): n(n), g(n), h(n) {}
int addEdge(int u, int v, Cap c, Cost w) {
// cout << "#" << u << " " << v << " " << c << " " << w << endl;
int res = sz(es);
g[u].push_back(sz(es)); es.push_back({v, c, w});
g[v].push_back(sz(es)); es.push_back({u, 0, -w});
return res;
}
pair<Cost, Cap> mincostflow(int src, int sink, Cap mx_flow = Cap_MAX) {
h.assign(n, Cost_MAX);
h[src] = 0;
rep(rd, 1, n) rep(now, 0, n - 1) for (auto i: g[now]) {
auto [v, c, w] = es[i];
if (c > 0) h[v] = min(h[v], h[now] + w);
}
Cost cost = 0;
Cap flow = 0;
while (mx_flow) {
priority_queue<pair<Cost, int> > pq;
vector<Cost> dis(n, Cost_MAX);
dis[src] = 0; pq.emplace(0, src);
vi pre(n, -1), mark(n, 0);
while(sz(pq)) {
auto [d, now] = pq.top(); pq.pop();
if (mark[now]) continue;
mark[now] = 1;
for (auto i: g[now]) {
auto [v, c, w] = es[i];
Cost off = dis[now] + w + h[now] - h[v];
if (c > 0 && dis[v] > off) {
dis[v] = off;
pq.emplace(-dis[v], v);
pre[v] = i;
}
}
}
if (pre[sink] == -1) break;
rep(i, 0, n - 1) if (dis[i] != Cost_MAX) h[i] += dis[i];
Cap aug = mx_flow;
for (int i = pre[sink]; ~i; i = pre[es[i ^ 1].to]) aug = min(aug, es[i].a);
for (int i = pre[sink]; ~i; i = pre[es[i ^ 1].to]) es[i].a -= aug, es[i ^ 1].a += aug;
mx_flow -= aug;
flow += aug;
cost += aug * h[sink];
}
return {cost, flow};
}
} ;
const long long inf1 = 1e6;
const long long inf2 = 1e12;
const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;
int n, r, g;
int fa[maxn];
int block_id[maxn];
long long wei[maxm];
vector<pair<long long, pair<int, int> > > all;
vector<int> id1, id2;
inline int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }
int main(){
scanf("%d%d%d", &n, &r, &g);
for(int i = 1; i <= r; ++i) {
int a, b;
long long c; scanf("%d%d%lld", &a, &b, &c);
all.push_back(make_pair(c, make_pair(a, b)));
}
sort(all.begin(), all.end());
for (int i = 1; i <= n + all.size(); ++i) fa[i] = i;
int tot = n * 3 + g + 5;
SuccessiveShortestPath<int, long long> flow(tot);
int tree_node = n + 1;
long long ans = 0;
for (auto e: all) {
int u = e.second.first, v = e.second.second;
long long w = e.first;
u = find(u), v = find(v);
if (u == v) continue;
int z = tree_node++;
fa[u] = z, fa[v] = z;
flow.addEdge(u, z, 1, -inf1);
flow.addEdge(v, z, 1, -inf1);
wei[z] = w;
ans += w;
}
int block_node = tree_node;
for (int i = 1; i < tree_node; ++i) {
if (find(i) == i) {
int u = block_node++;
block_id[i] = u;
}
}
for (int i = 1; i < tree_node; ++i) {
if (i > n) id2.push_back(flow.addEdge(i, block_id[find(i)], 1, -wei[i]));
if (find(i) == i) flow.addEdge(i, block_id[i], 1, -inf1);
}
int S = 0, T = tot - 1;
for (int i = tree_node; i < block_node; ++i) {
id1.push_back(flow.addEdge(i, T, 1, -inf2));
flow.addEdge(i, T, g, 0);
}
int k_node = block_node;
for (int i = 0; i < g; ++i) {
int cnt; scanf("%d", &cnt);
int u = k_node++;
flow.addEdge(S, u, 1, 0);
for (int j = 0; j < cnt; ++j) {
int x; scanf("%d", &x);
flow.addEdge(u, x, 1, 0);
}
}
auto [cost, cap] = flow.mincostflow(S, T);
// cout << cost << " " << cap << endl;
if (cap != g) {
puts("-1");
return 0;
}
for (auto e: id1) {
if(flow.es[e].a != 0) {
puts("-1");
return 0;
}
}
for (auto e: id2) {
if (flow.es[e].a == 0) {
ans += flow.es[e].w;
}
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4000kb
input:
5 6 2 1 2 1 1 3 4 2 4 2 2 5 5 3 4 7 4 5 3 2 1 2 2 2 4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
10 19 6 1 5 761 6 8 606 3 9 648 2 4 115 5 8 814 1 2 712 4 10 13 5 10 797 3 4 956 1 7 73 5 7 192 2 7 110 5 9 302 3 6 120 6 9 494 1 3 668 3 7 966 6 10 974 3 8 41 2 10 5 3 6 4 3 2 1 7 2 10 8 3 10 7 8 2 2 1
output:
429
result:
ok answer is '429'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3788kb
input:
10 43 3 1 3 656 2 6 856 4 10 99 5 6 900 2 7 766 4 7 582 2 8 135 5 7 831 3 5 12 3 10 789 1 8 66 4 9 390 1 7 238 6 7 960 1 4 624 3 9 602 7 10 366 5 8 526 2 9 561 6 10 722 2 5 904 3 4 35 1 9 768 5 9 457 6 8 61 4 6 192 4 5 96 5 10 747 8 9 611 7 8 953 3 8 449 2 4 228 1 6 197 9 10 160 3 6 869 1 2 785 4 8 ...
output:
587
result:
wrong answer expected '526', found '587'