Secret Milking Machine POJ - 2455 网络流（Dinic算法---广搜判断+深搜增广）+时间优化+二分

题意：

第一行输入N M C ，表示从1到N有M条无向边，现在要从1走到N 走C次完全不同的路径，求最长边的最小值。下面M行是从a点到b点的距离。

建图：

题上说从两点之间可以有多条边,问的是从1~N的C种走法，所走路径上的最大边最小可以是多少，所以我们用结构体来储存点的距离，用二分搜索中的mid来假设成最大边的值，那么其他边都要小于等于它，然后根据mid建图，两点之间的边数作为容量网络的边权，也就是两点间的容量，（Dinic跑一遍）求出一个最大流，看它与C的关系，如果C大于它，说明mid太小，反之mid太大。

关于Dinic 和优化·

首先通过广搜判断是否存在增广路，然后用深搜对地图进行操作，求最大流。深搜的时候有两个形参，一个是点的编号，另一个是由上一个点流过来的流量（具体见注释）

优化是先通过广搜的标记数组book[ ]的值，初始化为-1，大于等于0代表已经走过，不过标记的时候是

book[i]=book[k]+1（k走到 i），用于深搜的时候判断for循环中的顶点是否可走。在深搜的时候如果一个点没有网络流，就标记为-2或更小,下一次就不再在这个点搜了。（不优化则超时）

#include<queue>

#include<stdio.h>

#include<string.h>

using namespace std;

struct

{

    int u,v,w;

}mp[40100];

int e[220][221],n,m,sign[220][220],mid,inf=0x3f3f3f3f;

int book[220];

int bfs()

{

    memset(book,-1,sizeof(book));

    memset(sign,0,sizeof(sign));

    book[1]=0;

    queue<int>q;

    q.push(1);

    while(!q.empty())

    {

        int k=q.front();

        q.pop();

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

        {

            if(book[i]<0&&e[k][i]>0)//没有走过并且可以走

            {

                book[i]=book[k]+1;//从 k 点走过来 k->i

                q.push(i);

            }

        }

    }

   if(book[n]>=0) return 1;

    return 0;

}

void build()

{

    memset(e,0,sizeof(e));

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

        if(mp[i].w<=mid)

        {

            e[mp[i].v][mp[i].u]++;

            e[mp[i].u][mp[i].v]++;

        }

}

int dfs(int v,int sum)

{

    int t,s,i,use=0;

    if(v==n)//找到终点      s=sum

        return sum;

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

    {

        if(e[v][i]>0&&book[i]==book[v]+1)//v->i

        {

            t=dfs(i,min(sum,e[v][i]));//路径上最小的流

            use+=t;//回溯时加减

            e[v][i]-=t;

            e[i][v]+=t;

            sum-=t;

        }

        if(sum<=0)//如果sum小于零 不再递归

            break;

    }

    if(!use)book[v]=-2;// 路径以后不再走  节点中没有网络流

    return use;//返回最大流相当于s-sum

}

int main()

{

    int c;

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

    {

        int t1,t2,t3,l=inf,r=-1;

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

        {

            scanf("%d%d%d",&mp[i].u,&mp[i].v,&mp[i].w);

            if(l>mp[i].w)//超时

                l=mp[i].w;

            if(r<mp[i].w)

                r=mp[i].w;

        }

        while(l<r)

        {

            mid=(l+r)/2;

            build();

            int ans=0;

            while(bfs()) ans+=dfs(1,inf);

            if(ans>=c)

                r=mid;

            else

                l=mid+1;

        }

        printf("%d\n",r);

    }

    return 0;

}

巴特西

Secret Milking Machine POJ - 2455 网络流（Dinic算法---广搜判断+深搜增广）+时间优化+二分

最新文章

热门文章