제출 #1313289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313289		Jer	Tug of War (BOI15_tug)	C++20	0 / 100	9 ms	5104 KiB

tug

#include <bits/stdc++.h>

using namespace std;

struct edge
{
    int to, cap, rev;
};

struct dinic
{
    vector<int> level, it;
    vector<vector<edge>> g;
    int n;

    dinic(int n) : n(n), level(n + 5), it(n + 5), g(n + 5) {}

    void add_edge(int u, int v, int cap = 1)
    {
        edge a = {v, cap, (int)g[v].size()};
        edge b = {u, 0, (int)g[u].size()};
        g[u].push_back(a);
        g[v].push_back(b);
    }

    bool bfs(int s, int t)
    {
        fill(level.begin(), level.end(), -1);
        level[s] = 0;

        queue<int> q;
        q.push(s);

        while (!q.empty())
        {
            int curr = q.front();
            q.pop();

            for (auto e : g[curr])
                if (level[e.to] == -1 and e.cap > 0)
                    level[e.to] = level[curr] + 1, q.push(e.to);
        }

        return level[t] != -1;
    }

    int dfs(int curr, int t, int f)
    {
        if (curr == t)
            return f;

        for (int &i = it[curr]; i < g[curr].size(); i++)
        {
            auto &e = g[curr][i];
            if (level[e.to] == level[curr] + 1 and e.cap > 0)
            {
                int push = dfs(e.to, t, min(f, e.cap));
                if (push > 0)
                {
                    e.cap -= push;
                    g[e.to][e.rev].cap += push;
                    return push;
                }
            }
        }

        return 0;
    }

    int max_flow(int s, int t)
    {
        int flow = 0;
        cout << flow << '\n';
        while (bfs(s, t))
        {
            fill(it.begin(), it.end(), 0);
            while (int push = dfs(s, t, INT_MAX))
                flow += push;
        }
        return flow;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n, k;

    vector<int> l(2 * n), r(2 * n);
    int st;
    for (int i = 0; i < 2 * n; i++)
        cin >> l[i] >> r[i] >> st;

    int s = 0, e = 4 * n + 1;

    dinic d(e);

    for (int i = 1; i <= 2 * n; i++)
        d.add_edge(s, i);

    for (int i = 0; i < 2 * n; i++)
    {
        d.add_edge(i + 1, l[i] + (2 * n));
        d.add_edge(l[i] + (3 * n), e);
        d.add_edge(i + 1, r[i] + (3 * n));
        d.add_edge(r[i] + (3 * n), e);
    }

    cout << (d.max_flow(s, e) == 2 * n ? "YES\n" : "NO\n");

    return 0;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 23
• Subtask 4: 0 / 29