hlpp re 求助
查看原帖
hlpp re 求助
450290
MurataHimeko楼主2021/12/4 10:37

求助,总是 re 两个点。

#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i)
#define ste(i, f, t, s) for(int i(f); i <= t; i += s)
#define ets(i, t, f, s) for(int i(t); i >= f; i -= s)
#define each(i, x) for(auto &i : (x))
#define nx(i, u) for(int i(head[u]); i; i = e[i].next) 
typedef long long ll;
typedef long double lb;
// #define int long long
using namespace std;
#define inf 0x3f3f3f3f

const int N = 1e4+3;
int n, m, st, ed, u, v;
ll w;

struct edge {
    int to, next;
    int val;
}e[2000020];

int head[N], cnt = 1;

void add (int u, int v, int w) {
    e[++cnt] = (edge){v, head[u], w};
    head[u] = cnt;
}

int gap[N], h[N], vis[N], surp[N];

struct cmp {
    bool operator ()(int xi, int yi) const {
        return h[xi] < h[yi];
    }
};

priority_queue<int, vector<int>, cmp> pq;
queue<int>q;

bool bfs () {
    fill(h+1, h+n+1, inf);
    h[ed] = 0;
    q.push(ed);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        nx(i, u) {
            int v = e[i].to;
            if((e[i ^ 1].val) && h[v] > h[u] + 1) {
                h[v] = h[u] + 1;
                q.push(v);
            }
        }
    }
    return h[st] ^ inf;
}

void push (int u) {
    nx(i, u) {
        int v = e[i].to;
        if((e[i].val) && (h[v] + 1 == h[u])) {
            int sur = min(e[i].val, surp[u]);
            e[i].val -= sur;
            e[i ^ 1].val += sur;
            surp[u] -= sur;
            surp[v] += sur;
            if((v ^ st) && (v ^ ed) && (!vis[v])) {
                pq.push(v);
                vis[v] = 1;
            }
            if(!surp[u]) return ;
        }
    }
}

void relabel (int u) {
    h[u] = inf;
    nx(i, u) {
        int v = e[i].to;
        if(e[i].val && h[v] + 1 < h[u]) h[u] = h[v] + 1;
    }
}

int hlpp () {
    if(!bfs()) return 0;
    h[st] = n;
    fill(gap+1, gap+n+1, 0);
    re(i, n) if(h[i] ^ inf) ++gap[h[i]];
    nx(i, st) {
        int v = e[i].to;
        if(int sur = e[i].val) {
            e[i].val -= sur, e[i ^ 1].val += sur;
            surp[st] -= sur;
            surp[v] += sur;
            if((v ^ st) && (v ^ ed) && (!vis[v])) {
                pq.push(v);
                vis[v] = 1;
            }
        }
    }
    while(!pq.empty()) {
        int u = pq.top(); pq.pop();
        vis[u] = 0;
        push(u);
        if(surp[u]) {
            gap[h[u]]--;
            if(!gap[h[u]]) {
                re(v, n) {
                    if((v ^ st) && (v ^ ed) && (h[v] > h[u]) && (h[v] < n+1)) 
                        h[v] = n+1;
                }
            }
            relabel(u); ++gap[h[u]];
            pq.push(u); vis[u] = 1;
        }
    }
    return surp[ed];
}

signed main () {
    cin >> n >> m;
    ed = 520;
    re(i, n) {
        cin >> w;
        if(w) add(st, i, 1), add(i, st, 0);
        else add(i, ed, 1), add(ed, i, 0);
    }
    re(i, m) {
        cin >> u >> v;
        add(u, v, 1), add(v, u, 0);
        add(v, u, 1), add(u, v, 0);
    }
    cout << hlpp();
    return 0;
}
2021/12/4 10:37
加载中...