QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#485568#1825. The King's GuardsCelestialCoder#WA 1ms5720kbC++204.4kb2024-07-20 20:04:232024-07-20 20:04:24

Judging History

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

  • [2024-07-20 20:04:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5720kb
  • [2024-07-20 20:04:23]
  • 提交

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'