QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562817 | #1825. The King's Guards | arnold518# | WA | 1ms | 3856kb | C++17 | 4.0kb | 2024-09-13 21:13:53 | 2024-09-13 21:13:53 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int SZ = 1010;
namespace mcmf {
struct edge {
int v, c, w, d;
};
vector<edge> gph[SZ];
void add_edge(int u, int v, int c, int w) {
gph[u].push_back({v, c, w, (int)gph[v].size()});
gph[v].push_back({u, 0, -w, (int)gph[u].size() - 1});
}
int src, snk, dst[SZ], inq[SZ], bv[SZ], be[SZ];
pii bfs() {
fill(dst, dst + SZ, -1e9);
fill(inq, inq + SZ, 0);
dst[src] = 0;
inq[src] = true;
queue<int> Q;
Q.push(src);
while (!Q.empty()) {
int v = Q.front(); Q.pop();
for (int i = 0; i < gph[v].size(); i++) {
edge e = gph[v][i];
if (e.c > 0) {
if (dst[e.v] < dst[v] + e.w) {
dst[e.v] = dst[v] + e.w;
bv[e.v] = v;
be[e.v] = i;
if (!inq[e.v]) {
inq[e.v] = true;
Q.push(e.v);
}
}
}
}
}
if (dst[snk] == 1e9) return pii{0, 0};
else {
int fl = 1e9;
for (int v = snk; v != src; v = bv[v]) {
edge e = gph[bv[v]][be[v]];
fl = min(fl, e.c);
}
int cst = 0;
for (int v = snk; v != src; v = bv[v]) {
edge e = gph[bv[v]][be[v]];
cst += e.w * fl;
gph[bv[v]][be[v]].c -= fl;
gph[v][e.d].c += fl;
}
return pii{fl, cst};
}
}
pii calc(int _src, int _snk) {
src = _src; snk = _snk;
int fl = 0, cst = 0;
while (true) {
pii ret = bfs();
if (ret.ff == 0) {
break;
}
fl += ret.ff;
cst += ret.ss;
}
return {fl, cst};
}
}
struct dsu {
int par[SZ];
void init() {
iota(par, par + SZ, 0);
}
int find(int a) {
return par[a] = ((par[a] == a) ? a : find(par[a]));
}
void merge(int a, int b) {
a = find(a);
b = find(b);
par[b] = a;
}
} dsu;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
// {
// mcmf::add_edge(0, 1, 1, 2);
// auto [x, y] = mcmf::calc(0, 1);
// cout << x << ' ' << y << '\n';
// return 0;
// }
int n, m, k;
cin >> n >> m >> k;
dsu.init();
vector<pair<int, pii>> V;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
V.push_back({w, pii{u, v}});
}
sort(V.begin(), V.end());
int src = 0, snk = 2 * n + 1;
set<int> ST;
int sz = n + 1;
int ans = 0;
for (int i = 1; i <= n; i++) ST.insert(i);
for (auto [w, pr] : V) {
auto [u, v] = pr;
if (dsu.find(u) != dsu.find(v)) {
u = dsu.find(u);
v = dsu.find(v);
ST.erase(u);
ST.erase(v);
mcmf::add_edge(u, sz, 1, 0);
mcmf::add_edge(v, sz, 1, 0);
mcmf::add_edge(sz, snk, 1, w);
ST.insert(sz);
dsu.merge(sz, u);
dsu.merge(sz, v);
++sz;
ans += w;
}
}
for (int x : ST) {
mcmf::add_edge(x, sz, 1, 0);
mcmf::add_edge(sz, snk, 1, 10000);
++sz;
}
for (int i = 1; i <= k; i++) {
mcmf::add_edge(src, 2 * n + 1 + i, 1, 0);
int sz; cin >> sz;
while (sz--) {
int x; cin >> x;
mcmf::add_edge(2 * n + 1 + i, x, 1, 0);
}
}
auto [x, y] = mcmf::calc(src, snk);
// cout << x << ' ' << y << "?\n";
if (x != k) {
cout << "-1\n";
}
else cout << ans - (y - (int)ST.size() * 10000) << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3696kb
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: 3856kb
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: 3608kb
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:
534
result:
wrong answer expected '526', found '534'