64分又WA又T求助

qfpjm @ 2022-02-11 19:35:53

#include <bits/stdc++.h>

using namespace std;

struct node
{
    int e, v, nxt;
}edge[20005];

int n, m, s, t;
int cnt = 1, head[20005], dis[20005];

void add(int u, int v, int w)
{
    cnt ++;
    edge[cnt].e = v;
    edge[cnt].v = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

bool bfs(int s, int t)
{
    memset(dis, 0, sizeof(dis));
    dis[s] = 1;
    queue<int> que;
    que.push(s);
    while (!que.empty())
    {
        int r = que.front();
        que.pop();
        for (int i = head[r] ; i != -1 ; i = edge[i].nxt)
        {
            int j = edge[i].e;
            if (!dis[j] && edge[i].v)
            {
                dis[j] = dis[r] + 1;
                que.push(j);
                if (j == t)
                {
                    return true;
                }
            }
        }
    }
    if(dis[t])
    {
        return true;
    }
    else
    {
        return false;
    }
}

int dfs(int u, int ed, int flo)
{
    if (u == ed)
    {
        return flo;
    }
    int ans = 0;
    for (int i = head[u] ; i != -1 && ans < flo ; i = edge[i].nxt)
    {
        int v = edge[i].e;
        if (dis[v] == dis[u] + 1 && edge[i].v > 0)
        {
            int d = dfs(v, ed, min(flo - ans, edge[i].v));
            edge[i].v -= d;
            edge[i ^ 1].v += d;
            ans += d;
        }
    }
    return ans;
}

int dinic(int s, int t)
{
    int ans = 0;
    while (bfs(s, t))
    {
        ans += dfs(s, t, INT_MAX);
    }
    return ans;
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m >> s >> t;
    for (int i = 1 ; i <= m ; i ++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);
    }
    cout << dinic(s, t);
}

by Sharing666 @ 2022-02-11 19:42:48

@Ted_hjl

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct node
{
    int e, v, nxt;
}edge[20005];

int n, m, s, t;
int cnt = 1, head[20005], dis[20005];

void add(int u, int v, int w)
{
    cnt ++;
    edge[cnt].e = v;
    edge[cnt].v = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

bool bfs(int s, int t)
{
    memset(dis, 0, sizeof(dis));
    dis[s] = 1;
    queue<int> que;
    que.push(s);
    while (!que.empty())
    {
        int r = que.front();
        que.pop();
        for (int i = head[r] ; i != -1 ; i = edge[i].nxt)
        {
            int j = edge[i].e;
            if (!dis[j] && edge[i].v)
            {
                dis[j] = dis[r] + 1;
                que.push(j);
            }
        }
    }
    if(dis[t])
    {
        return true;
    }
    else
    {
        return false;
    }
}

int dfs(int u, int ed, int flo)
{
    if (u == ed)
    {
        return flo;
    }
    int ans = 0;
    for (int i = head[u] ; i != -1 ; i = edge[i].nxt)
    {
        int v = edge[i].e;
        if (dis[v] == dis[u] + 1 && edge[i].v > 0)
        {
            int d = dfs(v, ed, min(flo - ans, edge[i].v));
            edge[i].v -= d;
            edge[i ^ 1].v += d;
            ans += d;
        }
    }
    if(ans == 0) dis[u] = 0;
    return ans;
}

int dinic(int s, int t)
{
    int ans = 0;
    while (bfs(s, t))
    {
        ans += dfs(s, t, INT_MAX);
    }
    return ans;
}

signed main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m >> s >> t;
    for (int i = 1 ; i <= m ; i ++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);
    }
    cout << dinic(s, t);
}

by qfpjm @ 2022-02-11 19:44:33

@Sharing666 谢了

by Sharing666 @ 2022-02-11 19:44:51

开 long long。

dfs 加上这一行优化：

if(ans == 0) dis[u] = 0;

by Sharing666 @ 2022-02-11 19:45:05

@Ted_hjl 不用谢