萌新刚学网络流,求大佬查错……

P3376 【模板】网络最大流

BCZSX @ 2019-04-16 13:39:34

样例未过

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

#define MAXN 10100
#define MAXM 101000
#define INF 0x3f3f3f3f

struct node
{
    int v,w,next;
}edge[MAXM];
queue<int> que;
int n,m,s,t,ans,cnt,u,v,w;
int head[MAXM],dis[MAXN];

void add_edge(int u,int v,int w)
{
    edge[++ cnt].next = head[u];
    edge[cnt].v = v;
    edge[cnt].w = w;
    head[u] = cnt;
}

bool bfs()
{
    memset(dis,- 1,sizeof(dis));
    que.push(s);
    dis[s] = 0;
    while (! que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = head[u] ; i != - 1 ; i = edge[i].next)
        {
            int v = edge[i].v;
            if (dis[v] == - 1 && edge[i].w > 0)
            {
                dis[v] = dis[u] + 1;
                que.push(v);
            }
        }
    }
    return dis[t] != - 1;
}

int dfs(int u,int exp)
{
    if (u == t) return exp;
    int flow = 0,tmp;
    for (int i = head[u] ; i != - 1 ; i = edge[i].next)
    {
        int v = edge[i].v;
        if (dis[v] == dis[u] + 1 && edge[i].w > 0)
        {
            tmp = dfs(v,min(edge[i].w,exp));
            if (! tmp) continue;
            exp -= tmp;
            flow += tmp;
            edge[i].w -= tmp;
            edge[i ^ 1].w += tmp;
            if (! exp) break;
        }
    }
    return flow;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1 ; i <= m ; ++ i)
    {
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u,v,w);
        add_edge(v,u,0);
    }
    while (bfs()) ans += dfs(s,INF);
    printf("%d", ans);
    return 0;
}

by huhao @ 2019-04-16 13:55:00

@BCZSX cnt初始不应该是1


by BCZSX @ 2019-04-16 13:56:42

@huhao 为什么呀?QAQ


by huhao @ 2019-04-16 13:59:06

@BCZSX

你用^1来找对应的,从2开始编号才对应得上啊


by BCZSX @ 2019-04-16 14:01:20

@huhao 改完后代码还是死循环……


by hyfhaha @ 2019-04-16 14:02:38

head 清-1


by hyfhaha @ 2019-04-16 14:03:22

@BCZSX head 清-1


by BCZSX @ 2019-04-16 14:05:14

终于改好了,谢谢两位大佬@huhao@hyfhaha


|