求助,WA两个点

P3376 【模板】网络最大流

MashPlant @ 2018-01-28 16:08:26

求助一下,蒟蒻的代码只有80分,WA第5和10个点

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
    static char ch;
    bool sgn = false;
    while ((ch = getchar()) < '0' || ch > '9')
        if (ch == '-')
            sgn = true;
    int res = ch - 48;
    while ((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + ch - 48;
    return sgn ? -res : res;
}
const int inf = 0x3f3f3f3f;
const int ninf = 0xf3f3f3f3;
struct E
{
    int to;
    int w;
    int another;
};
typedef vector<E> ve;
ve es[10010];
int n, m, s, t;
bool vis[10010];
ll dfs(int x, ll cur)
{
    vis[x] = true;
    if (!cur || x == t)
        return cur;
    ve &e = es[x];
    for (int i = 0; i < e.size(); ++i)
    {
        if (e[i].w > 0 && !vis[e[i].to])
            if (int add = dfs(e[i].to, min(cur, ll(e[i].w))))
            {
                e[i].w -= add, es[e[i].to][e[i].another].w += add;
                return add; //找出一条增广路就停了
            }
    }
    return 0;
}
int main()
{
    n = read(), m = read(), s = read(), t = read();
    while (m--)
    {
        int u = read(), v = read(), w = read();
        es[u].push_back({v, w, int(es[v].size())});
        es[v].push_back({u, -w, int(es[u].size() - 1)});
    }
    int ans = 0;
    while (int more = dfs(s, inf))
        memset(vis, 0, sizeof(vis)), ans += more;
    printf("%d\n", ans);
    return 0;
}

by MashPlant @ 2018-01-28 16:48:27

好吧我知道了....反向边的初始容量为0.....

虽然没人回复但还是谢谢大家。


|