QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#800165#1825. The King's Guardsucup-team2172#WA 0ms4000kbC++234.8kb2024-12-05 22:45:132024-12-05 22:45:13

Judging History

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

  • [2024-12-05 22:45:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4000kb
  • [2024-12-05 22:45:13]
  • 提交

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;
}

详细

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'