hdu4280 最大流DINIC

题意:

x最小的到x最大的点同一时间的最大运输量.

思路:
裸的最大流,不解释,注意一点,记得加上防爆栈.
#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<stdio.h>

#include<string.h>

#include<queue>

#define N 300000

using namespace std;

struct  star

{

   int b,c,next;

}D[N];

struct mknum

{

    int x,t;

}tou,xin;

queue<mknum>q;

int minn(int x,int y)

{

  return x<y?x:y;

}

int list1[100005],list2[100005],tot;

int  deep[100005];

void add(int a,int b,int c)

{

   D[++tot].b=b;

   D[tot].c=c;

   D[tot].next=list1[a];

   list1[a]=tot;

}

bool bfs(int s,int t,int n)

{

   memset(deep,255,sizeof(deep));

   deep[s]=0;

   xin.x=s;

   xin.t=0;

   while(!q.empty())

   q.pop();

   q.push(xin);

   while(!q.empty())

   {

      tou=q.front();

      q.pop();

      for(int k=list1[tou.x];k;k=D[k].next)

      {

          int to=D[k].b;

          if(deep[to]==-1&&D[k].c)

          {

        xin.x=to;

        xin.t=tou.t+1;

        q.push(xin);

        deep[xin.x]=xin.t;

           }

       }

      }

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

      list2[i]=list1[i];

      return deep[t]!=-1;

}                    

int dfs(int s,int t,int flow)

{

     if(s==t)

     return flow;

     int nowflow=0;

     for(int k=list2[s];k;k=D[k].next)

     {

          list2[s]=k;

    int to=D[k].b;

    int c=D[k].c;

    if(deep[to]!=deep[s]+1||!c)

    continue;

    if(nowflow==flow)

    break;

    int temp=dfs(to,t,minn(c,flow-nowflow));

    nowflow+=temp;

    D[k].c-=temp;

    D[k^1].c+=temp;

    if(nowflow==flow)

    break;

       }

        if(nowflow==0)

        deep[s]=0;

        return nowflow;

}

int DINIC(int s,int t,int n)

{

  int ans=0;

  while(bfs(s,t,n))

  {

     ans+=dfs(s,t,1000000000);

   }

   return ans;

}

int main ()

{

   int i,n,m,mx,mi,s,t,tt,a,b,c,x,y;

   scanf("%d",&tt);

   while(tt--)

   {

      scanf("%d%d",&n,&m);

      mx=-10000000,mi=10000000;

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

      {

         scanf("%d%d",&x,&y);

         if(mx<x)

         {

               mx=x;

            t=i;

         }

         if(mi>x)

         {

            mi=x;

            s=i;

         }

       }

       memset(list1,0,sizeof(list1));

       tot=1;

       for(i=1;i<=m;i++)

       {

          scanf("%d%d%d",&a,&b,&c);

    add(a,b,c);

    add(b,a,c);

        }

        printf("%d\n",DINIC(s,t,n));

    }

    return 0;

}
巴特西

hdu4280 最大流DINIC

最新文章

热门文章
