求助,为什么会 MLE
查看原帖
求助,为什么会 MLE
899430
huanhuanonly楼主2024/5/17 11:34

如题,所有测试点都MLE了,但是按理来说就算跑满也不大可能吧

本地运行正常,Dinic部分是上一题留下来的

#include <bits/stdc++.h>

using uint    = unsigned int;
using llong   = long long int;
using ullong  = unsigned long long int;
using ldouble = long double;

void add_edge(auto& e, int from, int to, int w)
{
    e[from].push_back({to, w, int(e[to].size())});
    e[to].push_back({from, 0, int(e[from].size() - 1)});
}

int main(void)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

#ifdef __localhost
    ::freopen("in", "r", stdin);
    ::freopen("out", "w", stdout);
#endif

    int n, m;
    std::cin >> n >> m;

    struct edge
    {
        int to, w, rid;
    };

    std::vector<std::vector<edge>> e(n + m + 2 + 1);

    constexpr int inf = INT_MAX / 2;

    int sum = 0;

    int s = n + m + 1, t = n + m + 2;

    std::vector<std::pair<int, std::vector<int>>> data(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        std::cin >> data[i].first;
        sum += data[i].first;
        
        int x;
        while (std::cin.get() != '\r')
        {
            std::cin >> x;
            data[i].second.push_back(x);
        }
    }

    std::vector<int> v(m + 1);

    for (int i = 1; i <= m; ++i)
    {
        std::cin >> v[i];
        add_edge(e, n + i, t, v[i]);
    }

    for (int i = 1; i <= n; ++i)
    {
        add_edge(e, s, i, data[i].first);

        for (int x : data[i].second)
        {
            add_edge(e, i, n + x, inf);
        }
    }

    std::vector<int> layer(e.size()), current(e.size());

    auto bfs = [&]() -> bool
    {
        std::fill(layer.begin(), layer.end(), 0);
        std::fill(current.begin(), current.end(), 0);

        std::queue<int> que;
        que.push(s);
        layer[s] = 1;

        while (not que.empty())
        {
            int u = que.front();
            que.pop();

            for (const auto& i : e[u])
            {
                if (i.w == 0 or layer[i.to])
                    continue;
                
                layer[i.to] = layer[u] + 1;
                que.push(i.to);
            }
        }

        return layer[t];
    };

    std::function<int(int, int)> dfs = [&](int u, int limit) -> int
    {
        if (u == t)
            return limit;

        for (int i = current[u]; i < e[u].size(); ++i)
        {
            current[u] = i;

            auto& eg = e[u][i];

            if (eg.w == 0 or layer[eg.to] != layer[u] + 1)
                continue;

            if (int flow = dfs(eg.to, std::min(eg.w, limit)); flow)
            {
                eg.w -= flow;
                e[eg.to][eg.rid].w += flow;
                return flow;
            }
            else
            {
                layer[eg.to] = 0;
            }
        }

        return 0;
    };

    int maxflow = 0, flow;

    while (bfs())
    {
        while (flow = dfs(s, inf))
        {
            maxflow += flow;
        }
    }

    std::set<int> st;

    for (const auto& i : e[s])
    {
        if (i.w)
        {
            st.insert(i.to);
        }
    }

    for (const auto& i : st)
        std::cout << i << ' ';
    
    std::cout.put('\n');
    st.clear();

    for (const auto& i : e[t])
    {
        if (e[i.to][i.rid].w == 0)
        {
            st.insert(i.to - n);
        }
    }

    for (const auto& i : st)
        std::cout << i << ' ';
    
    std::cout.put('\n');

    std::cout << sum - maxflow;

    return 0;
}
2024/5/17 11:34
加载中...