dinic wa了五个点，实在不知道哪里有问题了（有注释）

cooronx @ 2022-09-24 17:00:08

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
const int maxn = 1214;
const long long INF = 1e10;

struct edge {
    int to;
    int cap;
    size_t rev;//反向边的编号
};

int cur[maxn];
int level[maxn];
bool isedge[maxn][maxn];
std::vector <edge> G[maxn];

void add_edge(int x, int y, int cap) {
    if (isedge[x][y]) {
        G[x][isedge[x][y]].cap += cap;
    }
    else {

        G[x].push_back(edge{ y,cap,G[y].size() });
        G[y].push_back(edge{ x,0,G[x].size() - 1 });
        isedge[x][y] = G[x].size()-1;
    }
}//邻接表存图，注意去掉重边

void find_level(int s,int t) {
    std::queue <int> q;
    q.push(s);
    memset(level, -1, sizeof(level));
    level[s] = 0;
    while (!q.empty()) {
        int head = q.front();
        q.pop();
        for (int i = 0; i < G[head].size(); ++i) {
            if (level[G[head][i].to] == -1 && G[head][i].cap > 0) {
                level[G[head][i].to] = level[head] + 1;
                q.push(G[head][i].to);
            }
        }
    }
}//生成分层图

int dfs(int s,int t,int f) {
    if (s == t)return f;
    for (int& i = cur[s]; i < G[s].size(); ++i) {
        edge& e = G[s][i];
        if (level[e.to] > level[s] && e.cap > 0) {
            int temp = dfs(e.to, t, std::min(f, e.cap));
            if (temp > 0) {
                e.cap -= temp;
                G[e.to][e.rev].cap += temp;
                return temp;
            }
        }
    }
    return 0;
}//带弧优化

int max_flow(int s, int t) {
    int maxflow = 0;
    while (1) {
        find_level(s, t);
        if (level[t] == -1)return maxflow;
        memset(cur, 0, sizeof(cur));
        while (1) {
            int flow = dfs(s, t, INF);
            if (flow == 0)break;
            else maxflow += flow;
        }
    }
}//求最大流

int main() {
    int n, m,s,t;
    while (std::cin >> n >> m>>s>>t) {
        memset(isedge, 0, sizeof(isedge));
        for (int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for (int i = 1; i <= m; ++i) {
            int x, y, z;
            std::cin >> x >> y >> z;
            add_edge(x, y, z);
        }
        std::cout << max_flow(s, t)<<std::endl;
    }
    return 0;
}

by yizhiming @ 2022-09-24 17:29:40

@cooronx isedge数组不能是bool吧？别的问题我暂时没看出来

by yizhiming @ 2022-09-24 17:30:23

改完之后wa4个。。

by cooronx @ 2022-09-24 18:18:43

@yizhiming 草，确实，忘改那个isedge数组了

by cooronx @ 2022-09-24 18:47:43

@yizhiming 真找不出来了，xd有思路吗

by aHapBean @ 2022-10-05 12:23:32

1.开long long

2.把你的去重改改，我把你的去重删掉后就能AC了，看起来你的去重逻辑有点乱，我就不看了（我个人用的链式向前星）

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
const int maxn = 1214;
const long long INF = 1e10;

struct edge {
    int to;
    int cap;
    size_t rev;//反向边的编号
};

int cur[maxn];
int level[maxn];
int isedge[maxn][maxn];
std::vector <edge> G[maxn];

void add_edge(int x, int y, int cap) {
    G[x].push_back(edge{ y,cap,G[y].size() });
    G[y].push_back(edge{ x,0,G[x].size() - 1 });
}//邻接表存图，注意去掉重边

void find_level(int s,int t) {
    std::queue <int> q;
    q.push(s);
    memset(level, -1, sizeof(level));
    level[s] = 0;
    while (!q.empty()) {
        int head = q.front();
        q.pop();
        for (int i = 0; i < G[head].size(); ++i) {
            if (level[G[head][i].to] == -1 && G[head][i].cap > 0) {
                level[G[head][i].to] = level[head] + 1;
                q.push(G[head][i].to);
            }
        }
    }
}//生成分层图

int dfs(int s,int t,int f) {
    if (s == t)return f;
    for (int& i = cur[s]; i < G[s].size(); ++i) {
        edge& e = G[s][i];
        if (level[e.to] > level[s] && e.cap > 0) {
            int temp = dfs(e.to, t, std::min(f, e.cap));
            if (temp > 0) {
                e.cap -= temp;
                G[e.to][e.rev].cap += temp;
                return temp;
            }
        }
    }
    return 0;
}//带弧优化

long long max_flow(int s, int t) {
    long long maxflow = 0;
    while (1) {
        find_level(s, t);
        if (level[t] == -1)return maxflow;
        memset(cur, 0, sizeof(cur));
        while (1) {
            int flow = dfs(s, t, (1ll << 31) - 1);
            if (flow == 0)break;
            else maxflow += flow;
        }
    }
    return maxflow;
}//求最大流

int main() {
    int n, m,s,t;
    std::cin >> n >> m >> s >> t;
    memset(isedge, -1, sizeof(isedge));
    for (int i = 1; i <= n; ++i) {
        G[i].clear();
    }
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        std::cin >> x >> y >> z;
        add_edge(x, y, z);
    }
    std::cout << max_flow(s, t) << std::endl;
    return 0;
}