求助,关于一些诡异的现象。
查看原帖
求助,关于一些诡异的现象。
249620
Muly楼主2023/7/12 13:59

在我代码中随着我调整MAX_V的值会给出我不同的评分。当我的MAX_V为5e3+10的时候TLE了两个点,而当将这个值改为5e3+100的时候却莫名奇妙地过了,然而我其他什么代码也没有改。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
namespace Primal_Dual {
    using ll = long long;
    const int MAX_V = 5e3 + 100;
    const ll INF = 1e12;
    struct Edge {
        int from, to;
        ll cup, flow, cost;
        Edge(int u, int v, ll c, ll f, ll w) : from(u), to(v), cup(c), flow(f), cost(w) {}
    };
    struct Graph {
        int n, m, s, t;
        vector<Edge> es;
        vector<int> G[MAX_V];
        ll dis[MAX_V], h[MAX_V];
        int prevv[MAX_V], preve[MAX_V];
        bool vis[MAX_V];

        Graph(int s, int t, int n = MAX_V) : s(s), t(t), n(n) {
            es.clear();
            for(int i = 0; i < n; i ++) {
                G[i].clear();
            }
        }
        void add_Edge(int u, int v, ll cup, ll cost) {
            es.push_back({u, v, cup, 0, cost}), es.push_back({v, u, 0, 0, -cost});
            m = es.size();
            G[u].push_back(m - 2), G[v].push_back({m - 1});
        }
        void spfa() {
            queue<int> q;
            for(int i = 0; i < n; i ++) {
                h[i] = INF;
            }
            h[s] = 0, vis[s] = true;
            q.push(s);
            while(q.size()) {
                int u = q.front();
                q.pop();
                vis[u] = false;
                for(int i : G[u]) {
                    const Edge& e = es[i];
                    if(e.cup > e.flow && h[e.to] > h[e.from] + e.cost) {
                        h[e.to] = h[e.from] + e.cost;
                        if(!vis[e.to]) {
                            q.push(e.to);
                            vis[e.to] = true;
                        }
                    }
                }
            }
        }
        struct mypair {
            ll dis; 
            int id;
            bool operator< (const mypair& a) const {
                return dis > a.dis;
            }
        };
        bool Dij() {
            for(int i = 0; i < n; i ++) {
                dis[i] = INF;
            }
            memset(vis, 0, sizeof vis);
            priority_queue<mypair> q;
            dis[s] = 0;
            q.push({dis[s], s});
            while(q.size()) {
                int u = q.top().id;
                q.pop();
                if(vis[u]) continue;
                vis[u] = true;
                for(int i : G[u]) {
                    const Edge& e = es[i];
                    ll nc = e.cost + h[e.from] - h[e.to];
                    if(e.cup > e.flow && dis[e.to] > dis[e.from] + nc) {
                        dis[e.to] = dis[e.from] + nc;
                        prevv[e.to] = e.from;
                        preve[e.to] = i;
                        q.push({dis[e.to], e.to});
                    }
                }
            }
            return dis[t] < INF;
        }
        auto maxf_minc() {
            spfa();
            ll maxf = 0;
            ll minc = 0;
            while(Dij()) {
                ll f = INF;
                for(int i = 0; i < n; i ++) if(dis[i] != INF) {
                    h[i] += dis[i];
                }
                for(int x = t; x != s; x = prevv[x]) {
                    f = min(f, es[preve[x]].cup - es[preve[x]].flow);
                }
                for(int x = t; x != s; x = prevv[x]) {
                    es[preve[x]].flow += f;
                    es[preve[x] ^ 1].flow -= f;
                }
                maxf += f;
                minc += f * h[t];
            }
            return tuple<ll, ll>(maxf, minc);
        }
    };
};
using namespace Primal_Dual;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> citys(n);
    map<string, int> mp;
    for(int i = 0; i < n; i ++) {
        cin >> citys[i];
        mp[citys[i]] = i;
    }
    Graph gra(0, 2 * n - 1);
    for(int i = 0; i < n; i ++) {
        gra.add_Edge(i * 2, i * 2 + 1, (i == 0 || i == n - 1 ? 2 : 1), -1);
    }
    for(int i = 0; i < m; i ++) {
        string a, b;
        cin >> a >> b;
        int x = mp[a], y = mp[b];
        if(x > y) swap(x, y);
        gra.add_Edge(x * 2 + 1, y * 2, INF, 0);
    }
    const auto [maxf, minc] = gra.maxf_minc();
    if(maxf == 2) {
        vector<vector<int>> G(n);
        vector<int> loop(1, 0);
        for(int i = 0; i < gra.m; i += 2) {
            const auto& e = gra.es[i];
            if(e.from / 2 != e.to / 2 && e.flow) {
                G[e.from / 2].push_back(e.to / 2);
                G[e.to / 2].push_back(e.from / 2);
            }
        }
        int x = G[0][0], prev = 0;
        while(x != 0) {
            loop.push_back(x);
            for(int i : G[x]) if(i != prev || minc == - 4) {
                prev = x;
                x = i;
                break;
            }
        }
        loop.push_back(0);
        cout << loop.size() - 1 << '\n';
        for(int i : loop) {
            cout << citys[i] << '\n';
        }
    } else {
        cout << "No Solution!\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _ = 1;
    // cin >> _;
    while(_ --) {
        solve();
    }
}
2023/7/12 13:59
加载中...