QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#562817#1825. The King's Guardsarnold518#WA 1ms3856kbC++174.0kb2024-09-13 21:13:532024-09-13 21:13:53

Judging History

你现在查看的是最新测评结果

  • [2024-09-13 21:13:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3856kb
  • [2024-09-13 21:13:53]
  • 提交

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'