QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#411675#4513. Slide ParadeTobo35 ✓2095ms39540kbC++2311.3kb2024-05-15 17:34:102024-05-15 17:34:11

Judging History

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

  • [2024-05-15 17:34:11]
  • 评测
  • 测评结果：35
  • 用时：2095ms
  • 内存：39540kb
查看
  • [2024-05-15 17:34:10]
  • 提交

answer

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

typedef long long flow_t;
typedef long long cost_t;

const flow_t inf_flow = 1e18;
const cost_t inf_cost = 1e18;

struct CostEdge
{
    int from, to;
    cost_t cost;
    flow_t cap, low = 0, flow = 0;
};

int num_node(const std::vector<CostEdge> &edges)
{
    int n = 0;
    for (const auto &e : edges)
        n = std::max({n, e.from, e.to});
    return n;
}
std::pair<flow_t, cost_t> get_flow(const std::vector<CostEdge> &edges, int s)
{
    flow_t flow = 0;
    cost_t cost = 0;
    for (const auto &e : edges)
    {
        if (e.from == s)
            flow += e.flow;
        cost += e.flow * e.cost;
    }
    return {flow, cost};
}

struct CostFlow
{
    struct Edge
    {
        int from, to;
        cost_t cost;
        flow_t cap;
    };
    int n;
    std::vector<std::vector<int>> eid;
    std::vector<Edge> edge;
    void build(const std::vector<CostEdge> &edges)
    {
        n = num_node(edges);
        eid.assign(n + 1, {});
        edge.clear();
        int num_edges = 0;
        for (const auto &e : edges)
        {
            eid[e.from].push_back(num_edges++);
            edge.push_back({e.from, e.to, e.cost, e.cap - e.flow});
            eid[e.to].push_back(num_edges++);
            edge.push_back({e.to, e.from, -e.cost, e.flow});
        }
    }
    std::vector<cost_t> dis;
    std::vector<int> pre;
    bool spfa(int s, int t)
    {
        if (s > n || t > n)
            return false;
        dis.assign(n + 1, inf_cost);
        pre.assign(n + 1, 0);
        std::vector<bool> inque(n + 1);
        std::queue<int> que;
        dis[s] = 0;
        que.push(s);
        inque[s] = true;
        while (que.size())
        {
            int u = que.front();
            // cerr << 'u' << ' ' << u << endl;
            que.pop();
            inque[u] = false;
            for (auto i : eid[u])
            {
                const auto &e = edge[i];
                if (e.cap && dis[e.to] > dis[u] + e.cost)
                {
                    dis[e.to] = dis[u] + e.cost;
                    pre[e.to] = i;
                    if (!inque[e.to])
                    {
                        que.push(e.to);
                        inque[e.to] = true;
                    }
                }
            }
        }
        return dis[t] < inf_cost;
    }
    std::pair<flow_t, cost_t> maxflow(int s, int t)
    {
        flow_t flow = 0;
        cost_t cost = 0;
        while (spfa(s, t))
        {
            flow_t detf = inf_flow;
            cost_t detc = 0;
            for (int u = t, i = pre[u]; u != s; u = edge[i].from, i = pre[u])
            {
                detf = std::min(detf, edge[i].cap);
                detc += edge[i].cost;
            }
            for (int u = t, i = pre[u]; u != s; u = edge[i].from, i = pre[u])
            {
                edge[i].cap -= detf;
                edge[i ^ 1].cap += detf;
            }
            flow += detf;
            cost += detf * detc;
        }
        return {flow, cost};
    }
    std::vector<CostEdge> to_edge()
    {
        std::vector<CostEdge> edges;
        for (int i = 0; i < edge.size(); i += 2)
            edges.push_back({
                .from = edge[i].from,
                .to = edge[i].to,
                .cost = edge[i].cost,
                .cap = edge[i].cap + edge[i ^ 1].cap,
                .flow = edge[i ^ 1].cap,
            });
        return edges;
    }
};

struct Processor
{
    std::vector<bool> neg;
    std::vector<flow_t> low;
    std::vector<flow_t> excess;
    void init(std::vector<CostEdge> &edges)
    {
        int n = num_node(edges);
        neg.clear();
        neg.reserve(edges.size());
        low.clear();
        low.reserve(edges.size());
        excess.assign(n + 1, 0);
    }
    void rmv_low(std::vector<CostEdge> &edges)
    {
        for (auto &e : edges)
        {
            low.push_back(e.low);
            if (e.flow >= e.low)
            {
                e.flow -= e.low;
            }
            else
            {
                excess[e.from] -= e.low - e.flow;
                excess[e.to] += e.low - e.flow;
                e.flow = 0;
            }
            e.cap -= e.low;
            e.low = 0;
        }
    }
    void add_low(std::vector<CostEdge> &edges)
    {
        reverse(low.begin(), low.end());
        for (auto &e : edges)
        {
            e.low = low.back();
            e.flow += e.low;
            e.cap += e.low;
            low.pop_back();
        }
    }
    void rmv_neg(std::vector<CostEdge> &edges)
    {
        for (auto &e : edges)
        {
            neg.push_back(e.cost < 0);
            if (e.cost < 0)
            {
                excess[e.from] -= e.cap - e.flow;
                excess[e.to] += e.cap - e.flow;
                e.flow = e.cap;
            }
            if (e.cost > 0)
            {
                excess[e.from] += e.flow;
                excess[e.to] -= e.flow;
                e.flow = 0;
            }
        }
    }
};

bool excess_flow(std::vector<CostEdge> &edges,
                 const std::vector<flow_t> &excess)
{
    int n = num_node(edges), m = edges.size();
    for (int i = 1; i <= n; i++)
    {
        if (excess[i] > 0)
            edges.push_back({.from = n + 1, .to = i, .cost = 0, .cap = excess[i]});
        if (excess[i] < 0)
            edges.push_back({.from = i, .to = n + 2, .cost = 0, .cap = -excess[i]});
    }
    CostFlow g;
    g.build(edges);
    g.maxflow(n + 1, n + 2);
    edges = g.to_edge();
    for (int i = m; i < edges.size(); i++)
        if (edges[i].flow != edges[i].cap)
            return false;
    edges.resize(m);
    return true;
}

std::optional<std::pair<flow_t, cost_t>> feasible_flow(
    std::vector<CostEdge> &edges, int s = 0, int t = 0)
{
    if (s && t)
        edges.push_back({.from = t, .to = s, .cost = 0, .cap = inf_flow});
    Processor p;
    p.init(edges);
    p.rmv_low(edges);
    p.rmv_neg(edges);
    if (!excess_flow(edges, p.excess))
        return std::nullopt;
    if (s && t)
        edges.pop_back();
    p.add_low(edges);
    return get_flow(edges, s);
}

std::optional<std::pair<flow_t, cost_t>> maximum_flow(
    std::vector<CostEdge> &edges, int s, int t)
{
    edges.push_back({.from = t, .to = s, .cost = 0, .cap = inf_flow});
    Processor p;
    p.init(edges);
    p.rmv_low(edges);
    p.rmv_neg(edges);
    if (!excess_flow(edges, p.excess))
        return std::nullopt;
    edges.pop_back();
    CostFlow g;
    g.build(edges);
    g.maxflow(s, t);
    edges = g.to_edge();
    p.add_low(edges);
    return get_flow(edges, s);
}

std::optional<std::pair<flow_t, cost_t>> minimum_flow(
    std::vector<CostEdge> &edges, int s, int t)
{
    edges.push_back({.from = t, .to = s, .cost = 0, .cap = inf_flow});
    Processor p;
    p.init(edges);
    p.rmv_low(edges);
    p.rmv_neg(edges);
    if (!excess_flow(edges, p.excess))
        return std::nullopt;
    edges.pop_back();
    CostFlow g;
    for (auto &e : edges)
        e.cost = -e.cost;
    Processor q;
    q.rmv_neg(edges);
    excess_flow(edges, q.excess);
    g.build(edges);
    g.maxflow(t, s);
    edges = g.to_edge();
    for (auto &e : edges)
        e.cost = -e.cost;
    p.add_low(edges);
    return get_flow(edges, s);
}

void solve()
{

    int n, m;
    cin >> n >> m;

    int s = 0, t = n * 2 + 1;
    vector<int> head(t + 1, -1), cap, to, nxt;
    auto add = [&](int x, int y, int z)
    {
        to.push_back(y);
        cap.push_back(z);
        nxt.push_back(head[x]);
        head[x] = to.size() - 1;
        to.push_back(x);
        cap.push_back(0);
        nxt.push_back(head[y]);
        head[y] = to.size() - 1;
    };
    vector<vector<int>> G(n + 1);
    for (int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        G[u].push_back(v);
        add(u, v + n, 1);
    }
    for (int i = 1; i <= n; i++)
        add(s, i, 1), add(i + n, t, 1);

    vector<int> g(t + 1), dis(t + 1);
    auto bfs = [&]() -> bool
    {
        dis.assign(t + 1, -1);
        dis[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty())
        {
            int cur = que.front();
            que.pop();
            g[cur] = head[cur];
            for (int p = head[cur]; ~p; p = nxt[p])
            {
                if (cap[p] && dis[to[p]] == -1)
                {
                    dis[to[p]] = dis[cur] + 1;
                    que.push(to[p]);
                }
            }
        }
        return dis[t] != -1;
    };
    auto dfs = [&](auto &dfs, int cur, int flow) -> int
    {
        if (cur == t)
            return flow;
        int used = 0;
        for (int &p = g[cur]; ~p; p = nxt[p])
        {
            if (cap[p] && dis[to[p]] == dis[cur] + 1)
            {
                int k = dfs(dfs, to[p], min(flow - used, cap[p]));
                used += k;
                cap[p] -= k, cap[p ^ 1] += k;
                if (used == flow)
                    break;
            }
        }
        return used;
    };
    int match_cnt = 0;
    while (bfs())
        match_cnt += dfs(dfs, s, 1e9);
    if (match_cnt < n)
    {
        cout << "IMPOSSIBLE\n";
        return;
    }

    vector<int> match(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int p = head[i]; ~p; p = nxt[p])
        {
            if (to[p] >= n + 1 && to[p] <= n * 2 && !cap[p])
                match[to[p] - n] = i;
        }
    }

    vector<vector<int>> adj(n + 1);
    vector<int> vis(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (auto j : G[i])
        {
            vis.assign(n + 1, 0);
            auto dfs = [&](auto &dfs, int cur, int target) -> bool
            {
                vis[cur] = 1;
                if (match[cur] == target)
                    return true;
                for (auto to : G[match[cur]])
                {
                    if (vis[to] || !dfs(dfs, to, target))
                        continue;
                    match[to] = match[cur], match[cur] = target;
                    return true;
                }
                return false;
            };
            if (!dfs(dfs, j, i))
            {
                cout << "IMPOSSIBLE\n";
                return;
            }
            for (int k = 1; k <= n; k++)
                adj[match[k]].push_back(k);
        }
    }

    vector<int> path{1};
    auto dfs1 = [&](auto &dfs1, int cur) -> void
    {
        while (!adj[cur].empty())
        {
            auto lst = adj[cur].back();
            adj[cur].pop_back();
            dfs1(dfs1, lst);
            path.push_back(cur);
        }
    };
    dfs1(dfs1, 1);
    if (path.size() != n * m + 1)
    {
        cout << "IMPOSSIBLE\n";
        return;
    }
    reverse(path.begin(), path.end());
    cout << n * m + 1 << '\n';
    for (int i : path)
        cout << i << ' ';
    cout << '\n';
}
/*
1
3 6
1 2
1 3
2 1
2 3
3 1
3 2
*/
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++)
    {
        cout << "Case #" << _ << ": ";
        solve();
    }
}
源文件, 语言: C++23

详细

Test #1:

score: 11
Accepted
time: 1ms
memory: 3616kb

input:

100
5 8
1 2
1 3
1 4
1 5
2 1
3 1
4 1
5 1
5 10
1 3
1 4
2 3
2 5
3 1
3 4
3 5
4 2
5 1
5 3
5 10
1 4
2 3
2 5
3 1
3 5
4 2
4 3
4 5
5 1
5 2
3 6
1 2
1 3
2 1
2 3
3 1
3 2
5 10
1 2
1 5
2 3
2 4
3 1
4 3
4 5
5 2
5 3
5 4
4 10
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 4
4 2
4 3
5 10
1 2
1 3
2 1
2 4
3 1
3 5
4 2
4 5
5 3
5 4
5 10
1 ...

output:

Case #1: IMPOSSIBLE
Case #2: 51
1 4 2 5 3 1 4 2 3 5 1 4 2 3 5 1 4 2 3 5 1 3 4 2 5 1 4 2 5 3 1 4 2 5 3 1 4 2 3 5 1 4 2 5 3 1 3 4 2 5 1 
Case #3: 51
1 4 3 1 4 2 5 2 3 5 1 4 5 2 3 1 4 3 1 4 2 5 2 3 5 1 4 2 3 5 1 4 3 1 4 3 1 4 5 2 5 2 5 2 3 1 4 5 2 3 1 
Case #4: 19
1 3 2 1 2 3 1 2 3 1 3 2 1 3 2 1 2 3 1 ...

result:

ok  (100 test cases)

Test #2:

score: 24
Accepted
time: 2095ms
memory: 39540kb

input:

100
199 4980
1 95
1 96
1 105
1 124
1 130
1 131
1 135
1 137
1 139
1 140
1 141
1 147
1 155
1 172
1 174
1 179
1 183
1 188
1 193
1 196
1 197
2 3
2 5
2 13
2 14
2 17
2 20
2 24
2 26
2 30
2 41
2 44
2 45
2 52
2 56
2 67
2 70
2 71
2 74
2 78
2 84
2 85
2 90
2 92
2 93
2 97
2 107
2 111
2 113
2 122
2 124
2 128
2 13...

output:

Case #1: IMPOSSIBLE
Case #2: IMPOSSIBLE
Case #3: 1000001
1 71 5 27 192 189 54 39 176 58 130 68 105 36 97 7 132 86 20 108 31 49 133 160 129 10 40 107 94 185 167 89 12 51 79 18 25 119 175 136 141 187 21 131 181 2 183 110 151 196 163 26 113 117 1 61 82 61 83 37 149 6 90 46 123 57 50 128 148 81 78 177 3...

result:

ok  (100 test cases)
English 繁體中文 简体中文

服务器时间: 2024-11-30 05:02:23 | 开源项目