萌新求助网络流EK算法

P3376 【模板】网络最大流

那一条变阻器 @ 2020-07-09 15:04:55

WA了8,9,10点,查了好久都找不到qnq

#include <bits/stdc++.h>
using namespace std;
long long n , m , s , t , ans;
long long pre[2010] , dis[2010][2010] , vis[2010];
vector<long long> e[200010];
bool bfs(){
    memset(vis , 0 , sizeof(vis));
    queue<long long> q;
    vis[s] = 1;
    q.push(s);
    while(!q.empty()){
        long long x = q.front();
        q.pop();
        for(long long i = 0; i < e[x].size(); i++){
            long long nx = e[x][i];
            if(dis[x][nx] && !vis[nx]){
                pre[nx] = x;
                q.push(nx);
                vis[nx] = 1;
                if(nx == t) return 1;
            }
        }
    }
    return 0;
}
void update(){
    long long x = t;
    long long minn = 0x3ffffffff;
    for(long long i = t; i != s; i = pre[i]) minn = min(minn , dis[pre[i]][i]);
    while(x != s){
        long long px = pre[x];
        dis[x][px] += minn;
        dis[px][x] -= minn;
        x = px;
    }
    ans += minn;
}
int main(){
    cin >> n >> m >> s >> t;
    for(long long i = 1; i <= m; i++){
        long long x , y;
        long long z;
        cin >> x >> y >> z;
        e[x].push_back(y);
        dis[x][y] = z;
        e[y].push_back(x);
    }
    while(bfs()) update();
    cout << ans;
    return 0;
}

by zythonc @ 2020-07-09 15:40:31

咋不写Dinic和ISPA


by 那一条变阻器 @ 2020-07-09 15:49:14

@zythonc 这种算法思想要理解下啊

求帮萌新看下qwq


by 辰星凌 @ 2020-07-09 15:54:13

连边出问题了


by 那一条变阻器 @ 2020-07-09 15:55:11

@辰星凌 请问一下该怎么连边

谢谢!!!


by 那一条变阻器 @ 2020-07-09 15:56:39

@辰星凌 找到了,谢谢!!!应该为dis[x][y] += z;

谢谢!!!!


|