P3376 【模板】网络最大流

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 100010;
typedef long long ll;
typedef pair<int, int> pii;
std::mt19937 rng {std::chrono::steady_clock::now().time_since_epoch().count()};

template <typename T>
void debug(T x) {
    cerr << x << '\n';
}

template <typename T, typename... Args>
void debug(T x, Args... args) {
    cerr << x << ' ';
    debug(args...);
}

const int V = 1010;
const int E = 101000;
template<typename T> 
struct FlowGraph {
    int s, t, vtot; 
    int head[V], etot;
    int dis[V], cur[V];
    struct edge {
        int v, nxt;
        T f;
    } e[E * 2];
    void addedge(int u, int v, T f) {
        e[etot] = {v, head[u], f}; head[u] = etot ++;
        e[etot] = {u, head[v], 0}; head[v] = etot ++;
    }

    bool bfs() {
        for (int i = 1; i <= vtot; i ++ ) {
            dis[i] = 0;
            cur[i] = head[i];
        }
        queue<int> q;
        q.push(s); dis[s] = 1;
        while (! q.empty()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt) {
                if (e[i].f && ! dis[e[i].v]) {
                    int v = e[i].v;
                    dis[v] = dis[u] + 1;
                    if (v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, T m) {
        if (u == t) return m;
        T flow = 0;
        for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) {
            if (e[i].f && dis[e[i].v] == dis[u] + 1) {
                T f = dfs(e[i].v, min(m, e[i].f));
                e[i].f -= f;
                e[i ^ 1].f += f;
                m -= f;
                flow += f;
                if (! m) break;
            }
        }
        if (! flow) dis[u] = -1;
        return flow;
    }
    T dinic() {
        T flow = 0;
        while (bfs()) flow += dfs(s, numeric_limits<T>::max());
        return flow;
    }
    void init(int s_, int t_, int vtot_) {
        s = s_;
        t = t_;
        vtot = vtot_;
        for (int i = 1; i <= vtot; i ++ ) head[i] = -1;
    }
};

FlowGraph<ll> g;
int n, m, s, t;

void solve() {
    cin >> n >> m >> s >> t;
    g.init(s, t, n);
    for (int i = 1; i <= m; i ++ ) {
        int u, v, w;
        cin >> u >> v >> w;
        g.addedge(u, v, w);
    }
    cout << g.dinic() << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T -- ) {
        solve();
    }
    return 0;
}

P2763 试题库问题

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 100010;
typedef long long ll;
typedef pair<int, int> pii;
std::mt19937 rng {std::chrono::steady_clock::now().time_since_epoch().count()};

template <typename T>
void debug(T x) {
    cerr << x << '\n';
}

template <typename T, typename... Args>
void debug(T x, Args... args) {
    cerr << x << ' ';
    debug(args...);
}

const int V = 1010;
const int E = 101000;
template<typename T> 
struct FlowGraph {
    int s, t, vtot;
    int head[V], etot;
    int dis[V], cur[V];
    struct edge {
        int v, nxt;
        T f;
    } e[E * 2];
    void addedge(int u, int v, T f) {
        e[etot] = {v, head[u], f}; head[u] = etot ++;
        e[etot] = {u, head[v], 0}; head[v] = etot ++;
    }

    bool bfs() {
        for (int i = 1; i <= vtot; i ++ ) {
            dis[i] = 0;
            cur[i] = head[i];
        }
        queue<int> q;
        q.push(s); dis[s] = 1;
        while (! q.empty()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt) {
                if (e[i].f && ! dis[e[i].v]) {
                    int v = e[i].v;
                    dis[v] = dis[u] + 1;
                    if (v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, T m) {
        if (u == t) return m;
        T flow = 0;
        for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) 
            if (e[i].f && dis[e[i].v] == dis[u] + 1) {
                T f = dfs(e[i].v, min(m, e[i].f));
                e[i].f -= f;
                e[i ^ 1].f += f;
                m -= f;
                flow += f;
                if (! m) break;
            }
        if (! flow) dis[u] = -1;
        return flow;
    }
    T dinic() {
        T flow = 0;
        while (bfs()) flow += dfs(s, numeric_limits<T>::max());
        return flow;
    }
    void init(int s_, int t_, int vtot_) {
        s = s_;
        t = t_;
        vtot = vtot_;
        for (int i = 1; i <= vtot; i ++ ) head[i] = -1;
    }
};

FlowGraph<int> g;
int n, k;
vector<int> ans[30];
vector<array<int, 3>> used;

void solve() {
    cin >> k >> n;
    int cnt_m = 0;
    g.init(n + k + 1, n + k + 2, n + k + 2);
    for (int i = 1; i <= k; i ++ ) {
        int x;
        cin >> x;
        cnt_m += x;
        g.addedge(n + k + 1, i, x);
    }
    for (int i = 1; i <= n; i ++ ) {
        g.addedge(k + i, n + k + 2, 1);
        int p;
        cin >> p;
        for (int j = 1; j <= p; j ++ ) {
            int x;
            cin >> x;
            used.push_back({x, i, g.etot});
            g.addedge(x, k + i, 1);
        }
    }
    if (g.dinic() != cnt_m) {
        cout << "No Solution!" << '\n';
        return; 
    }
    for(auto [p, q, id] : used) {
        if (g.e[id].f == 0) {
            ans[p].push_back(q);
        }
    }
    for (int i = 1; i <= k; i ++ ) {
        cout << i << ":";
        for (auto x : ans[i]) {
            cout << ' ' << x;
        }
        cout << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T -- ) {
        solve();
    }
    return 0;
}

P3425 [POI2005] KOS-Dicing

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 100010;
typedef long long ll;
typedef pair<int, int> pii;
std::mt19937 rng {std::chrono::steady_clock::now().time_since_epoch().count()};

template <typename T>
void debug(T x) {
    cerr << x << '\n';
}

template <typename T, typename... Args>
void debug(T x, Args... args) {
    cerr << x << ' ';
    debug(args...);
}

const int V = 20010;
const int E = 101000;
template<typename T> 
struct FlowGraph {
    int s, t, vtot;
    int head[V], etot;
    int dis[V], cur[V];
    struct edge {
        int v, nxt;
        T f;
    } e[E * 2];
    void addedge(int u, int v, T f) {
        e[etot] = {v, head[u], f}; head[u] = etot ++;
        e[etot] = {u, head[v], 0}; head[v] = etot ++;
    }

    bool bfs() {
        for (int i = 1; i <= vtot; i ++ ) {
            dis[i] = 0;
            cur[i] = head[i];
        }
        queue<int> q;
        q.push(s); dis[s] = 1;
        while (! q.empty()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt) {
                if (e[i].f && ! dis[e[i].v]) {
                    int v = e[i].v;
                    dis[v] = dis[u] + 1;
                    if (v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, T m) {
        if (u == t) return m;
        T flow = 0;
        for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) 
            if (e[i].f && dis[e[i].v] == dis[u] + 1) {
                T f = dfs(e[i].v, min(m, e[i].f));
                e[i].f -= f;
                e[i ^ 1].f += f;
                m -= f;
                flow += f;
                if (! m) break;
            }
        if (! flow) dis[u] = -1;
        return flow;
    }
    T dinic() {
        T flow = 0;
        while (bfs()) flow += dfs(s, numeric_limits<T>::max());
        return flow;
    }
    void init(int s_, int t_, int vtot_) {
        s = s_;
        t = t_;
        vtot = vtot_;
        etot = 0;
        for (int i = 1; i <= vtot; i ++ ) head[i] = -1;
    }
};

FlowGraph<int> g;
int n, m;

void solve() {
    cin >> n >> m;
    vector<pii> p(m + 1);
    for (int i = 1; i <= m; i ++ ) {
        cin >> p[i].fi >> p[i].se;
    }    

    vector<array<int, 3>> used;
    auto check = [&] (int x) {
        int s = n + m + 1;
        int t = n + m + 2;
        g.init(s, t, t);
        for (int i = 1; i <= m; i ++ ) {
            g.addedge(s, i, 1);
            g.addedge(i, p[i].fi + m, 1);
            g.addedge(i, p[i].se + m, 1);
        }
        for (int i = 1; i <= n; i ++ ) {
            g.addedge(i + m, t, x);
        }
        return g.dinic() == m;
    };

    int l = 0, r = m;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << '\n';
    int s = n + m + 1;
    int t = n + m + 2;
    g.init(s, t, t);
    for (int i = 1; i <= m; i ++ ) {
        g.addedge(s, i, 1);
        used.push_back({i, p[i].fi + m, g.etot});
        g.addedge(i, p[i].fi + m, 1);
        g.addedge(i, p[i].se + m, 1);
    }
    for (int i = 1; i <= n; i ++ ) {
        g.addedge(i + m, t, r);
    }
    g.dinic();
    for (auto [p, q, id] : used) {
        if (g.e[id].f == 0) {
            cout << 1 << '\n';
        } else {
            cout << 0 << '\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T -- ) {
        solve();
    }
    return 0;
}

CCPC ProblemG.疯狂星期六

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 100010;
typedef long long ll;
typedef pair<int, int> pii;
std::mt19937 rng {std::chrono::steady_clock::now().time_since_epoch().count()};

template <typename T>
void debug(T x) {
    cerr << x << '\n';
}

template <typename T, typename... Args>
void debug(T x, Args... args) {
    cerr << x << ' ';
    debug(args...);
}

const int V = 2010;
const int E = 101000;
template<typename T> 
struct FlowGraph {
    int s, t, vtot;
    int head[V], etot;
    int dis[V], cur[V];
    struct edge {
        int v, nxt;
        T f;
    } e[E * 2];
    void addedge(int u, int v, T f) {
        e[etot] = {v, head[u], f}; head[u] = etot ++;
        e[etot] = {u, head[v], 0}; head[v] = etot ++;
    }

    bool bfs() {
        for (int i = 1; i <= vtot; i ++ ) {
            dis[i] = 0;
            cur[i] = head[i];
        }
        queue<int> q;
        q.push(s); dis[s] = 1;
        while (! q.empty()) {
            int u = q.front(); q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt) {
                if (e[i].f && ! dis[e[i].v]) {
                    int v = e[i].v;
                    dis[v] = dis[u] + 1;
                    if (v == t) return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    T dfs(int u, T m) {
        if (u == t) return m;
        T flow = 0;
        for (int i = cur[u]; ~i; cur[u] = i = e[i].nxt) 
            if (e[i].f && dis[e[i].v] == dis[u] + 1) {
                T f = dfs(e[i].v, min(m, e[i].f));
                e[i].f -= f;
                e[i ^ 1].f += f;
                m -= f;
                flow += f;
                if (! m) break;
            }
        if (! flow) dis[u] = -1;
        return flow;
    }
    T dinic() {
        T flow = 0;
        while (bfs()) flow += dfs(s, numeric_limits<T>::max());
        return flow;
    }
    void init(int s_, int t_, int vtot_) {
        s = s_;
        t = t_;
        vtot = vtot_;
        etot = 0;
        for (int i = 1; i <= vtot; i ++ ) head[i] = -1;
    }
};

FlowGraph<int> g;
int n, m, a[N], v[N];

void solve() {
    cin >> n >> m;
    int yyq = 0, cost_food = 0;
    vector<int> cost(n + 1);
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i] >> v[i];
    }
    vector<array<int, 3>> alls;
    for (int i = 1; i <= m; i ++ ) {
        int x, y, w;
        cin >> x >> y >> w;
        alls.push_back({x, y, w});
        cost_food += w;
        cost[x] += w;
        cost[y] += w;
    }
    yyq = min(a[1], v[1] + cost[1]);
    cost[1] = yyq;
    for (int i = 2; i <= n; i ++ ) {
        cost[i] = min(a[i], min(v[i] + cost[i], yyq - 1));
    }
    for (int i = 2; i <= n; i ++ ) {
        if (cost[i] < v[i]) {
            cout << "NO" << '\n';
            return;
        }
    }
    int s = n + m + 1;
    int t = n + m + 2;
    g.init(s, t, t);
    for (int i = 1; i <= m; i ++ ) {
        auto [x, y, w] = alls[i - 1];
        g.addedge(s, i, w);
        g.addedge(i, x + m, w);
        g.addedge(i, y + m, w);
        //debug(s, i, w);
        //debug(i, x + m, w);
        //debug(i, y + m, w);
    }
    for (int i = 1; i <= n; i ++ ) {
        g.addedge(m + i, t, cost[i] - v[i]);
        //debug(m + i, t, cost[i]);
    }
    if (g.dinic() == cost_food) {
        cout << "YES" << '\n';
    } else {
        cout << "NO" << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T -- ) {
        solve();
    }
    return 0;
}