Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#160#1. 第二个 A + B ProblemNagoriYuuuki9736ms4644kbC++232.8kb2025-04-17 14:12:292025-04-19 16:15:12

answer

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

using i64 = long long;
#define endl '\n'
#define xx first
#define yy second

template <typename FlowType>
class NetFlow
{
private:
    struct Edge
    {
        int to, next;
        FlowType flow;
    };

    vector<Edge> edge;
    vector<int> head;
    vector<int> dep;
    vector<int> now;
    int tot = 1;
    int n;

    bool bfs()
    {
        fill(dep.begin(), dep.end(), 0);
        queue<int> que;
        que.push(s);
        dep[s] = 1;
        now[s] = head[s];
        while (!que.empty())
        {
            int u = que.front();
            que.pop();
            for (int i = head[u]; i; i = edge[i].next)
            {
                int v = edge[i].to;
                if (edge[i].flow > 0 && dep[v] == 0)
                {
                    que.push(v);
                    now[v] = head[v];
                    dep[v] = dep[u] + 1;
                    if (v == t)
                        return true;
                }
            }
        }
        return false;
    }

    FlowType dfs(int u, FlowType sum)
    {
        if (u == t)
            return sum;
        FlowType res = 0;
        for (int &i = now[u]; i && sum > 0; i = edge[i].next)
        {
            int v = edge[i].to;
            if (edge[i].flow > 0 && dep[v] == dep[u] + 1)
            {
                FlowType k = dfs(v, min(sum, edge[i].flow));
                if (k == 0)
                    dep[v] = 0;
                edge[i].flow -= k;
                edge[i ^ 1].flow += k;
                res += k;
                sum -= k;
            }
        }
        return res;
    }

public:
    int s, t;

    NetFlow(int n, int e, int s, int t)
    {
        this->n = n;
        edge.resize(2 * e + 5);
        head.resize(n + 5, 0);
        dep.resize(n + 5, 0);
        now.resize(n + 5, 0);
        this->s = s;
        this->t = t;
        tot = 1;
    }

    void add(int u, int v, FlowType flow)
    {
        edge[++tot] = {v, head[u], flow};
        head[u] = tot;

        edge[++tot] = {u, head[v], 0};
        head[v] = tot;
    }

    FlowType MaxFlow()
    {
        FlowType res = 0;
        while (bfs())
            res += dfs(s, numeric_limits<FlowType>::max());
        return res;
    }
};

signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x, y;
    cin >> x >> y;
    const int offset = 1e4 + 10;
    x += offset;
    y += offset;
    int n = x + y;
    int s = 0, t = n + 1;
    NetFlow<int> flow(t, 2 * n, s, t);

    for (int i = 1; i <= n; i++)
    {
        flow.add(s, i, 1);
        flow.add(i, t, 1);
    }

    int maxflow = flow.MaxFlow();

    cout << maxflow - (offset << 1) << endl;

    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 6ms
memory: 4276kb

input:

23 24

output:

47

result:

ok 1 number(s): "47"

Test #2:

score: 10
Accepted
time: 3ms
memory: 4376kb

input:

233 1

output:

234

result:

ok 1 number(s): "234"

Test #3:

score: 10
Accepted
time: 6ms
memory: 4448kb

input:

222 333

output:

555

result:

ok 1 number(s): "555"

Test #4:

score: 10
Accepted
time: 6ms
memory: 4336kb

input:

1 333

output:

334

result:

ok 1 number(s): "334"

Test #5:

score: 10
Accepted
time: 0ms
memory: 4276kb

input:

222 333

output:

555

result:

ok 1 number(s): "555"

Test #6:

score: 10
Accepted
time: 3ms
memory: 4416kb

input:

242 333

output:

575

result:

ok 1 number(s): "575"

Test #7:

score: 10
Accepted
time: 5ms
memory: 4540kb

input:

222 3330

output:

3552

result:

ok 1 number(s): "3552"

Test #8:

score: 10
Accepted
time: 4ms
memory: 4632kb

input:

2220 333

output:

2553

result:

ok 1 number(s): "2553"

Test #9:

score: 10
Accepted
time: 2ms
memory: 4476kb

input:

222 555

output:

777

result:

ok 1 number(s): "777"

Test #10:

score: 10
Accepted
time: 1ms
memory: 4644kb

input:

222 3333

output:

3555

result:

ok 1 number(s): "3555"

Extra Test:

score: -3
Extra Test Failed : Dangerous Syscalls on 2

input:

100000000 100000000

output:


result: