Dinic死循环,一直找不出来,求dalao帮找错

P3376 【模板】网络最大流

冈崎梦美 @ 2018-03-09 22:34:59

RT……大概写的和刘汝佳的《算法竞赛入门经典(训练指南)》上的Dinic差不多,但是有点区别,结果就爆了……求改正

#include<bits/stdc++.h>
#define MAXN 10001
#define MAXM 100001
#define INF 1e9
using namespace std;

int level[MAXN];
vector<int>G[MAXN];
int m,n,s,t;

struct node
{
    int from,to,cap,flow;
};
vector<node>edges;

void addedge(int u,int v,int cap)
{

    edges.push_back((node){u,v,cap,0});
    edges.push_back((node){v,u,0,0});
    int m=edges.size();
    G[u].push_back(m-2);
    G[v].push_back(m-1);
}

bool Dinic_BFS()
{
    bool vis[MAXN]={false};
    queue<int>team;team.push(s);
    level[s]=0;vis[s]=true;
    while(!team.empty())
    {
        int q=team.front();
        for(int i=0;i<G[q].size();i++)
        {
            node& e=edges[G[q][i]];
            if (!vis[e.to]&&e.cap>e.flow)
            {
                vis[e.to]=true;
                level[e.to]=level[q]+1;
                team.push(e.to);
            }
        }
    }
    return vis[t];
}

int Dinic_DFS(int u, int cpflow) {
    if(u==t) return cpflow; 
    int flow=0;
    for(int i=0;i<G[u].size() && flow<cpflow; i++){
        int v=edges[G[u][i]].to;
        if((level[u]+1==level[v])&&(edges[G[u][i]].cap>edges[G[u][i]].flow))
        {
            int tmpflow=Dinic_DFS(v,min(cpflow-flow,edges[G[u][i]].cap-edges[G[u][i]].flow));
            edges[G[u][i]].flow+=tmpflow;
            edges[G[u][i]^1].flow-=tmpflow;
            flow+=tmpflow;
        }
    }
    return flow;
}

int Dinic(int s,int t)
{
    int ans=0;
    while(Dinic_BFS())
    {
        memset(level,0,sizeof(level));
        ans+=Dinic_DFS(s,INF);
    }
    return ans;
}

int read()
{
    char ch;int x=0;
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x;
}
int main()
{
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),c=read();
        addedge(u,v,c);
    }
    cout<<Dinic(s,t);
    return 0;
}

by star_magic_young @ 2018-03-10 07:50:33

你用队列不pop? /huaji


by 冈崎梦美 @ 2018-03-10 10:13:22

@star_magic_young 通过了,谢谢Dalao


by 冈崎梦美 @ 2018-03-10 10:14:16

需要注意的是,我的level的初始化也错了——level应该在Dinic_BFS函数里初始化


by heyichong @ 2018-03-21 19:31:49

一定要初始化


|