网络流EK算法求助,8, 9,10点WA了

P3376 【模板】网络最大流

那一条变阻器 @ 2020-07-09 10:27:53

RT 加了long long的

#include <bits/stdc++.h>
using namespace std;
long long n , m , s , t , ans;
long long pre[210] , dis[210][210] , vis[210] , minn[210];
vector<int> e[210];
bool bfs(){
    memset(vis , 0 , sizeof(vis));
    queue<int> q;
    vis[s] = 1;
    q.push(s);
    minn[s] = 0x3ffffffffff;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < e[x].size(); i++){
            int nx = e[x][i];
            if(dis[x][nx]){
                if(vis[nx]) continue;
                minn[nx] = min(minn[x] , dis[x][nx]);
                pre[nx] = x;
                q.push(nx);
                vis[nx] = 1;
                if(nx == t) return 1;
            }
        }
    }
    return 0;
}
void update(){
    int x = t;
    while(x != s){
        int px = pre[x];
        dis[x][px] += minn[t];
        dis[px][x] -= minn[t];
        x = px;
    }
    ans += minn[t];
}
int main(){
    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i++){
        int 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 FunnyCreatress @ 2020-07-09 10:32:37

EK不是被卡掉了吗


by 那一条变阻器 @ 2020-07-09 10:37:38

@FunnyCreatress 但是应该是T掉啊,我WA掉了。

草地排水那道题也WA了一个点。


by Eleven谦 @ 2020-07-09 11:24:52

大概..数组小了点?


|