HDU-1532 Drainage Ditches，人生第一道网络流！

自己拉的专题里面没有这题，网上找博客学习网络流的时候看到闯亮学长的博客然后看到这个网络流入门题！随手一敲WA了几发看讨论区才发现坑点！

本题采用的是Edmonds-Karp算法求增广路。小白书上只介绍了这个算法，确实对于数据不刁钻的题目这个算法足以应对。大白书上的Dinic及SAP、ISAP还没有去看，以后慢慢攻克吧!

回到这个题：n条水渠，m个交点，每条水渠有一个最大容量cap，求1号交点到m号交点的最大流。

学了EK算法这题就可以裸引用了，只是注意一个坑点：重边的时候既不是取最大、也不是取最小，而是+=

int a[N],p[N],flow[N][N],cap[N][N];

int n,m;

void init()

{

    memset(flow,0,sizeof(flow));//流量，初始设为0

    memset(cap,0,sizeof(cap));//容量，开始为0表示这条通道不存在

}

void EK()

{

//    memset(p,0,sizeof(p));

    queue<int>q;

    ll f=0;//最大流

    while(1)

    {

        memset(a,0,sizeof(a));

        a[1]=INF;

        q.push(1);

        while(!q.empty())

        {

            int u=q.front();

            q.pop();

            for(int v=1; v<=m; v++)

                if(!a[v]&&cap[u][v]>flow[u][v])

                {

                    p[v]=u;

                    q.push(v);

                    a[v]=min(a[u],cap[u][v]-flow[u][v]);

                }

        }

        if(!a[m]) break;

        for(int i=m; i!=1; i=p[i])

        {

            flow[p[i]][i]+=a[m];

            flow[i][p[i]]-=a[m];

        }

        f+=a[m];

    }

    printf("%I64d\n",f);

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        init();

        int s,t,e;

        for(int i=0; i<n; i++)

        {

            scanf("%d%d%d",&s,&t,&e);

            cap[s][t]=cap[s][t]+e;

        }

        EK();

    }

    return 0;

}

给出闯亮学长的博客，写的很好，很适合初学者：http://blog.csdn.net/y990041769/article/details/21026445

巴特西

HDU-1532 Drainage Ditches，人生第一道网络流！

最新文章

热门文章