对着朋友100分标程打结果70分3,4,5WA求助

huangx607087 @ 2019-08-07 20:00:17

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,A;
int e[900000],w[900000],nxt[900000];
int hd[900000],dep[900000],q[3430000];
int bfs()
{
    int f=1,r=1;
    memset(dep,0,sizeof(dep));
    dep[s]=1;q[1]=s;
    while(f<=r)
    {
        int x=q[f++],k=hd[x];
        while(k)
        {
            if((dep[e[k]]==0)&&(w[k]>0))
            {
                dep[e[k]]=dep[x]+1;
                q[++r]=e[k];
            }
            k=nxt[k];
        }
    }
    return dep[t];
}

int dfs(int x,int flow)
{
    if(x==t) return flow;
    int k=hd[x];
    while(k)
    {
        if((w[k])&&(dep[e[k]]==dep[x]+1))
        {
            int dis=dfs(e[k],min(flow,w[k]));
            if(dis>0) 
            {
                w[k]-=dis;
                w[k^1]+=dis;
                return dis;
            }
        }
        k=nxt[k];
    }
    return 0;
}

void dinic()
{
    int B=0;
    while(bfs())
    {
        while(B=dfs(s,20011230)) A+=B;
    }
}

int main ()
{
    int k=0;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[++k]=y,w[k]=z,nxt[k]=hd[x],hd[x]=k;
        e[++k]=x,w[k]=0,nxt[k]=hd[y],hd[y]=k;
    }
    dinic();
    printf("%d\n",A);
    return 0;
}

by aminoas @ 2019-08-07 20:04:23

J++?!

by glassy @ 2019-08-12 15:10:31

@huangx607087 存边的时候要从偶数开始。

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,A;
int e[900000],w[900000],nxt[900000];
int hd[900000],dep[900000],q[3430000];
int bfs()
{
    int f=1,r=1;
    memset(dep,0,sizeof(dep));
    dep[s]=1;q[1]=s;
    while(f<=r)
    {
        int x=q[f++],k=hd[x];
        while(k)
        {
            if((dep[e[k]]==0)&&(w[k]>0))
            {
                dep[e[k]]=dep[x]+1;
                q[++r]=e[k];
            }
            k=nxt[k];
        }
    }
    return dep[t];
}

int dfs(int x,int flow)
{
    if(x==t) return flow;
    int k=hd[x];
    while(k)
    {
        if((w[k])&&(dep[e[k]]==dep[x]+1))
        {
            int dis=dfs(e[k],min(flow,w[k]));
            if(dis>0) 
            {
                w[k]-=dis;
                w[k^1]+=dis;
                return dis;
            }
        }
        k=nxt[k];
    }
    return 0;
}

void dinic()
{
    int B=0;
    while(bfs())
    {
        while(B=dfs(s,20011230)) A+=B;
    }
}

int main ()
{
    int k=1;
    //从1开始，因为0^1=1,1^1=0,2^1=3,3^1=2
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[++k]=y,w[k]=z,nxt[k]=hd[x],hd[x]=k;
        e[++k]=x,w[k]=0,nxt[k]=hd[y],hd[y]=k;
    }
    dinic();
    printf("%d\n",A);
    return 0;
}