求助!谜之WA和RE

P3376 【模板】网络最大流

PotatoServer @ 2019-02-01 15:11:18

第二个点WA了...最后两个点RE了...感觉显然哪里除了沙雕错误但就是找不出来

#include <bits/stdc++.h>
#include <queue>
using namespace std;
const int inf = 1e9;
int n,m,s,t;
queue<int>q;

struct edge {
    int next = -1;
    int to;
    int dis;
};

edge road[100005];
int head[10005];
int roadindex = 0;

int deep[10005]; 

void addroad(int u, int v, int w, int zero){
    road[roadindex].dis = w;
    if (zero)road[roadindex].dis = 0;
    road[roadindex].to = v;
    road[roadindex].next = head[u];
    head[u] = roadindex;

    roadindex++;
}

void clear(){
    memset (deep, -1, sizeof(deep));
}

bool bfs(){
    clear();

    while (!q.empty())q.pop();
    deep[s] = 1;
    q.push(s);
    while (!q.empty()){
        int inow = q.front();
        for (int i = head[inow]; i != -1; i = road[i].next){
            int nxt = road[i].to;
            if (road[i].dis <= 0)continue;

            if (deep[nxt] <= 0){
                deep[nxt] = deep[inow] + 1;
                q.push(nxt);
            }else if (deep[nxt] > deep[inow] + 1){
                deep[nxt] = deep[inow] + 1;
                q.push(nxt); 
            }
        }

        q.pop();
    }

    if (deep[t] > 0){
        return true;
    }else{
        return false;
    }
}

int dfs (int now, int limit){
    if (now == t || limit == 0)return limit;

    int flow = 0;
    for (int i = head[now]; i != -1; i = road[i].next){
        int nxt = road[i].to;
        if (road[i].dis > 0 && deep[nxt] == deep[now] + 1){
            flow = min (dfs (nxt, min (limit, road[i].dis)), limit);
            if (flow > 0){
                road[i].dis -= flow;
                road[i^1].dis += flow;
                break;
            }
        }else{
            continue;
        }
    }
    return flow;
}

int main (){
    scanf ("%d %d %d %d", &n, &m, &s, &t);
    memset (head, -1, sizeof(head));
    clear();

    for (int i = 0; i < m; i++){
        int u=0,v=0,w=0;
        scanf ("%d %d %d", &u, &v, &w);
        addroad(u,v,w,0);
        addroad(v,u,w,1);
    }

    int ans = 0;
    while (bfs()){
        while (true){
            int emm = dfs (s, inf);
            if (emm == 0)break;
            ans += emm;
        }
    }

    printf ("%d", ans);
    return 0;
} 

by xiaolou @ 2019-02-01 15:13:01

@PotatoServer 网络流正反两次建边,pool开200000


by PotatoServer @ 2019-02-01 22:23:59

@xiaolou !!!成了 谢谢


|