Bảo vệ

Điểm: 0,22 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một mạng lưới gồm ~N~ thành phố, và một số đường một chiều nối các cặp thành phố (giữa hai thành phố có thể có nhiều đường nối một chiều).

Quân địch đang tập trung ở thành phố ~N~, định tiến công ta ở thành phố ~1~, và chúng sẽ tiến công trên tất cả các con đường chưa được bảo vệ để tiến vào thành phố ~1~. Bộ chỉ huy ta cần xác định số quân ít nhất trên các con đường để chặn địch tiến về thành phố ~1~.

Input

Dòng đầu ghi ~N~ ~\left(N \leq 5000\right)~.

Các dòng tiếp theo cho đến hết file có không quá ~10000~ dòng, mỗi dòng một tả ~1~ đường gồm ~u, v, s~ cho biết có đoạn đường một chiều từ ~u~ đến ~v~, và phải cần ít nhất ~s~ ~\left(s \leq 65000\right)~ quân để chặn địch trên đường này.

Output

Số quân ít nhất cần điều động.

Sample Input

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

-3

vominhmanh10 đã bình luận lúc 16, Tháng 9, 2025, 12:32 ← sửa 2 →

nhớ định ý max-flow = min-cut là được, bị ngược đỉnh thu 1, phát n, dùng dinic

#include <bits/stdc++.h>
using namespace std;

const int maxn = 8005, inf = 1e9 + 7;
vector<vector<int>> adj(maxn);
int c[maxn][maxn], f[maxn][maxn], d[maxn], it[maxn], maxflow = 0, n;

void bfs() {
    fill(d, d + n + 1, inf);
    d[n] = 0;
    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (d[v] != inf || f[u][v] == c[u][v]) continue;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
}

int dfs(int u, int cur) {
    if (!cur) return 0;
    if (u == 1) return cur;

    for (; it[u] < (int)adj[u].size(); it[u]++) {
        int v = adj[u][it[u]];
        if (d[v] != d[u] + 1 || f[u][v] >= c[u][v]) continue;
        int del = dfs(v, min(cur, c[u][v] - f[u][v]));
        if (!del) continue;
        f[u][v] += del;
        f[v][u] -= del;
        return del;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int u, v, s; cin >> n;
    while (cin >> u >> v >> s) {
        adj[v].push_back(u);
        adj[u].push_back(v);
        c[u][v] = s;
    }
    while (1) {
        bfs();
        if (d[1] == inf) break;
        for (int i = 1; i <= n; i++) it[i] = 0;
        while (int del = dfs(n, inf)) maxflow += del;
    }
    cout << maxflow;
}

-15

hmackervjppro đã bình luận lúc 17, Tháng 10, 2023, 14:26

test đề sai à mn:))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

2

mhdttq đã bình luận lúc 12, Tháng 11, 2021, 14:54

bài này rất hay