dalao帮我看看预流推进算法哪里有错TAT

P3376 【模板】网络最大流

star_eternal @ 2017-10-20 08:03:01

#include<cstdio>
#include<queue>
#include<cstring>
#define N 10000+10
#define M 300000+10
using namespace std;
struct Arc{
    int next,to,cap;
}arc[M<<1];
int head[N],arnum=1;
void add(int from,int to,int cap)
{
    arc[++arnum]=(Arc){head[from],to,cap};
    head[from]=arnum;
}
void insert(int from,int to,int cap)
{
    add(from,to,cap);
    add(to,from,0);
}
int n,m;
struct cmp{
    int u,h;
    cmp(int u=0,int h=0):u(u),h(h){};
    inline bool operator < (const cmp & a)const {return h<a.h;}
};
priority_queue<cmp>Q;
int h[N],flow[N],gap[N];
bool push(int u,int v,int i)
{
    int minf=min(arc[i].cap,flow[u]);
    flow[u]-=minf;flow[v]+=minf;
    arc[i].cap-=minf;
    arc[i^1].cap+=minf;
}
void Gap(int l,int s,int t)
{
    for(int i=1;i<=n;i++)
    {
        if(i!=s &&i!=t&& l<h[i]&&h[i]<=n)h[i]=n+1;
    }
}
int maxflow(int s,int t)
{
    while(!Q.empty())Q.pop();
    memset(h,0,sizeof(h));memset(flow,0,sizeof(flow));memset(gap,0,sizeof(gap));
    h[s]=n;flow[s]=1e9;Q.push(cmp(s,h[s]));
    while(!Q.empty())
    {
        int u=Q.top().u;Q.pop();
        if(!flow[u])continue;
        for(int i=head[u];i;i=arc[i].next)
        {
            int v=arc[i].to;
            if((u==s||h[u]==h[v]+1)&&push(u,v,i)&&v!=s&&v!=t) Q.push(cmp(v,h[v]));
        }
        if (u!=s && u!=t && flow[u]){
            if (!(--gap[h[u]])) Gap(h[u],s,t);
            ++gap[++h[u]];
               Q.push(cmp(u,h[u]));
        }
    }
    return flow[t];
}
int main()
{
    int s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int u,v,cap;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&cap);
        if(!cap)continue;
        insert(u,v,cap);
    }
    printf("%d\n",maxflow(s,t));
}

by xtxwwwd @ 2018-02-05 14:00:22

滑稽 没有问题


|