萌新刚学OI,跑不出来求调

P3376 【模板】网络最大流

Obviathy @ 2023-02-16 17:56:17

#include<bits/stdc++.h>
# define ll long long
using namespace std;
const int N = 1e4,inf = 1023021618;
int n,t,m,s;
struct edge{
    int u,v,nxt;
    ll w;
}e[N];
int tot=-1;
int h[N],cur[N];
ll maxflorr;
int d[N];
inline void add(int u,int v,int w){
    //正 
    e[++tot].u = u;
    e[tot].v = v;
    e[tot].w = w;
    e[tot].nxt = h[u];
    h[u] = tot;
    //反
    e[++tot].u = v;
    e[tot].v = u;
    e[tot].w = 0;
    e[tot].nxt = h[v];
    h[v] = tot; 
}
inline bool bfs(){
    for(int i = 1;i <= n;i ++)d[i] = -1;
    queue<int>q;
    q.push(s);
//  cur[s] = h[s];
    d[s] = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = h[u];i>-1;i = e[i].nxt){
            int v = e[i].v;
            if(e[i].w > 0 && d[v] == -1){
                q.push(v);
                d[v] = d[u] + 1;
                //cur[v] = h[v];
                if(v == t)return 1;
            }
        }
    }
    return 0;
}
inline ll dfs(int u,ll flow){
    if(u == t||flow==0)return flow;
    ll f,res = 0;
    for(int i = cur[u];i!=-1;i = e[i].nxt){
        cur[u] = i;
        int v = e[i].v;
        if( d[v] == d[u] + 1 && (f = dfs(v,min(flow,e[i].w)))){
            e[i].w -= f;
            e[i^1].w += f;
            res += f;
            flow -= f;
            if(flow==0)return res;
        }
    }
    return res;
}
int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s >> t;
    for(int i = 1;i <= m;i ++){
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);
    }
    while(bfs()){
        for(int i = 1;i <= n;i ++)cur[i] = h[i];
        maxflorr += dfs(s,inf);
    }
    cout << maxflorr << endl;
    return 0;
}

by Obviathy @ 2023-02-16 17:56:39

dinic


by Alexandra @ 2023-02-16 18:04:08

memset一下h数组


by 小熙熙 @ 2023-02-16 18:04:27

此贴已完结,本人已过


by Deuteron @ 2023-02-16 18:06:17

你们太巨了/bx


by 小熙熙 @ 2023-02-16 18:08:22

@小可爱萌萌哒 你在哪?现在


by 小熙熙 @ 2023-02-16 18:08:49

@小可爱萌萌哒 在本部?


by Obviathy @ 2023-02-16 19:06:58

结案了


by 此间的少年fu @ 2023-02-16 20:01:25

萌新刚学OI???


by 此间的少年fu @ 2023-02-16 20:01:47

yxy好谦虚~


by _Extroversion @ 2023-02-17 15:30:37

一般要说MnZn刚学OI1秒钟


|