QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#485568 | #1825. The King's Guards | CelestialCoder# | WA | 1ms | 5720kb | C++20 | 4.4kb | 2024-07-20 20:04:23 | 2024-07-20 20:04:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, g;
struct es {
int u, v, w;
};
int operator<(const es& a, const es& b) {
return a.w < b.w;
}
int group[301];
int get_group(int x) {
if (group[x] == x)
return x;
return group[x] = get_group(group[x]);
}
vector<es> edges;
int max_dist[301][301];
vector<pair<int, int>> graph[1001];
int flow[1001][1001];
int cap[1001][1001];
int size = 0;
int dist[1001];
int in_queue[1001];
int hist[1001];
int total_sz;
int ans = 0;
const int inf = 1'000'000'001;
int total_flow = 0;
int find_flow(int src, int sink) {
for (int i = 0; i <= total_sz; ++i) {
dist[i] = inf;
hist[i] = -1;
in_queue[i] = 0;
}
queue<int> q;
q.push(src);
dist[src] = 0;
while (!q.empty()) {
int current = q.front();
q.pop();
in_queue[current] = 0;
int size = graph[current].size();
for (int i = 0; i < size; ++i) {
int next = graph[current][i].first;
int next_dist = graph[current][i].second + dist[current];
if (flow[current][next] < cap[current][next] && dist[next] > next_dist) {
dist[next] = next_dist;
hist[next] = current;
if (!in_queue[next]) {
in_queue[next] = 1;
q.push(next);
}
}
}
}
if (hist[sink] == -1)
return inf;
int current = sink;
int max_flow = 1000000001;
while (hist[current] != -1) {
int prev = hist[current];
max_flow = min(max_flow, cap[prev][current] - flow[prev][current]);
current = prev;
}
current = sink;
while (hist[current] != -1) {
int prev = hist[current];
flow[prev][current] += max_flow;
flow[current][prev] -= max_flow;
current = prev;
}
total_flow += max_flow;
return dist[sink];
}
int main() {
int r;
cin >> n >> r >> g;
for (int i = 1; i <= n; ++i) {
group[i] = i;
for (int j = 1; j <= n; ++j) {
max_dist[i][j] = 1000000001;
}
}
while (r--) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back({u, v, w});
}
sort (edges.begin(), edges.end());
for (int i = 0; i < edges.size(); ++i) {
int gu = get_group(edges[i].u);
int gv = get_group(edges[i].v);
if (gu != gv) {
group[gu] = gv;
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
if (get_group(j) == get_group(k)) {
max_dist[j][k] = min(max_dist[j][k], edges[i].w);
}
}
}
}
}
for (int i = 1; i <= g; ++i) {
graph[2 * n + g + 2].emplace_back(i, 0);
cap[2 * n + g + 2][i] = 1;
}
for (int i = 1; i <= n; ++i) {
graph[2 * n + g + 2].emplace_back(g + n + i, 0);
cap[2 * n + g + 2][g + n + i] = 1;
}
for (int i = 1; i <= g; ++i) {
int k;
cin >> k;
while (k--) {
int j;
cin >> j;
graph[i].emplace_back(g + j, 0);
graph[g + j].emplace_back(i, 0);
cap[i][g + j] = 1;
}
}
for (int i = 1; i <= n; ++i) {
graph[g + n + i].emplace_back(2 * n + g + 1, 0);
graph[2 * n + g + 1].emplace_back(g + n + i, 0);
cap[g + n + i][2 * n + g + 1] = 1;
}
graph[2 * n + g + 1].emplace_back(0, 0);
graph[0].emplace_back(2 * n + g + 1, 0);
cap[2 * n + g + 1][0] = inf;
graph[0].emplace_back(2 * n + g + 3, 0);
cap[0][2 * n + g + 3] = g;
for (int i = 1; i <= n; ++i) {
graph[g + i].emplace_back(2 * n + g + 3, 0);
cap[g + i][2 * n + g + 3] = 1;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j || max_dist[i][j] == inf)
continue;
graph[g + n + i].emplace_back(g + j, max_dist[i][j]);
graph[g + j].emplace_back(g + n + i, -max_dist[i][j]);
cap[g + n + i][g + j] = 1;
}
}
total_sz = 2 * n + g + 3;
long long ans = 0;
int v;
while ((v = find_flow(2 * n + g + 2, 2 * n + g + 3)) != inf)
ans += v;
if (total_flow != g + n)
cout << -1;
else
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5720kb
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: -100
Wrong Answer
time: 1ms
memory: 3800kb
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:
369
result:
wrong answer expected '429', found '369'