题目连接
学习路径: 预流推进 O(![N^{2}* \sqrt[]{M}](https://51itzy.com/uploads/202412/23/d8d6e00325d3a7fb.jpg)
讯享网)
https://www.luogu.org/blog/ONE-PIECE/jiu-ji-di-zui-tai-liu-suan-fa-isap-yu-hlpp
https://www.luogu.org/problemnew/solution/P4722

AC:朴素版本预流推进(刚刚好卡过)
#include<cstdio> #include<cstring> #include<queue> #include<iostream> using namespace std; const int maxn = 1e4 + 5, maxm = 2e6 + 5, inf = 0x3f3f3f3f; int n, m, s, t; int cnt = 0; int head[maxn], gap[maxn], h[maxn], e[maxn]; bool inq[maxn]; struct cmp { inline bool operator () (int a, int b) const { return h[a] < h[b]; } }; priority_queue<int,vector<int>,cmp> pq; struct Node { int v, flow, next; }edge[maxm]; //建边 inline void addedge(int u, int v, int flow) { edge[cnt] = {v, flow, head[u]}; head[u] = cnt++; edge[cnt] = {u, 0, head[v]}; head[v] = cnt++; } // 反向分层 inline bool Bfs() { memset(h, inf, sizeof(h)); queue<int> q; q.push(t), h[t] = 0; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; i; i = edge[i].next){ int v = edge[i].v; if (edge[i ^ 1].flow && h[v] > h[u] + 1) { h[v] = h[u] + 1; q.push(v); } } } return h[s] != inf; } //u点推流 inline void push_(int u) { register int i; for(i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].v; int flow = edge[i].flow; if (flow && (h[v]+1 == h[u])){ int mi = min(e[u], flow); edge[i].flow -= mi; edge[i^1].flow += mi; e[u] -= mi; e[v] += mi; if (v != s && v != t && !inq[v]) { pq.push(v); inq[v] = 1; } if ( e[u] == 0 ) break; } } } //更改 点的高度 inline void relabel(int u) { register int i; h[u] = inf; for (i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; int flow = edge[i].flow; if (flow && (h[v] + 1 < h[u])) { h[u] = h[v] + 1; } } } // HLPP开始预流推进 inline int Hlpp(){ register int i; if ( !Bfs() ) return 0; h[s] = n; memset(gap, 0, sizeof(gap)); for(i = 1; i <= n; ++i) if(h[i] != inf) gap[h[i]]++; for(i = head[s]; i != -1; i = edge[i].next){ int v = edge[i].v; int flow = edge[i].flow; if (flow) { edge[i].flow -= flow; edge[i ^ 1].flow += flow; e[s] -= flow; e[v] += flow; if(v != s && v != t && !inq[v]) { pq.push(v); inq[v]=1; } } } while (!pq.empty()) { int u = pq.top(); pq.pop(); inq[u] = 0; push_(u); if(e[u]) { gap[h[u]]--; if(!gap[h[u]]){ for(register int v = 1; v <= n; ++v){ if(v != s && v != t && h[v] > h[u] && h[v] < n+1){ h[v] = n + 1; } } } relabel(u); gap[h[u]]++; pq.push(u); inq[u] = 1; } } return e[t]; } //读入优化 int main() { //freopen("in.txt", "r", stdin); std::ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); memset(head, -1, sizeof(head)); cin >> n >> m >> s >> t; register int i; int u, v, val; for(int i = 1; i <= m; ++i) cin >> u >> v >> val, addedge(u, v, val); printf("%d", Hlpp()); return 0; }
讯享网
学习加强版 :待补。。。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/78052.html