posts - 64, comments - 4, trackbacks - 0, articles - 0

最大流模板朴素的和dinic的

Posted on 2010-08-18 16:26 acronix 阅读(352) 评论(0)  编辑 收藏 引用 所属分类: hzshuai收集的模板

朴素的最大流代码:
//BOJ 1154
#include <cstdio>

const int inf = 1<<25;

int cap[205][205
];
int pre[205],s,t,i,j,n,m,x,y,v,que[205
];
bool vis[205
];
/***********************************************/

bool bfs()
{
     
for (i = 1; i <= m; i++
)
         vis[i] 
= false
;
     
int f = 0,r = 1
,st; 
     que[r] 
= s; vis[1= true
;
     
while (f <
 r)
     {
           st 
= que[++
f];
           
for (i = 1; i<= m; i++
)
               
if (vis[i] != true && cap[st][i] > 0
)
               {
                  pre[i] 
=
 st;
                  vis[i] 
= true
;
                  
if (i ==
 t)
                     
return true
;
                  que[
++r] =
 i;        
               }
     }
     
return false
;
}

int
  max_flow()
{
     
int sum = 0
,min;
     
while
 (bfs())
     {
           min 
=
 inf;
           i 
=
 t;
           
while (i !=
 s)
           {
                 
if (cap[pre[i]][i] <
 min)
                    min 
=
 cap[pre[i]][i];
                 i 
=
 pre[i];
           }
           i 
=
 t;
           sum 
+=
 min;
           
while (i !=
 s)
           {
                 cap[pre[i]][i] 
-=
 min;
                 cap[i][pre[i]] 
+=
 min;
                 i 
=
 pre[i];
           }
     }
     
return
 sum;
}
/*****************************************************************/

int main()
{
    
while (scanf("%d %d",&n,&m) !=
 EOF)
    {
          
for (i = 1;i <= m; i++
)
              
for (j = 1; j <= m; j ++
)
                  cap[i][j] 
= 0
;
          
for (i = 1; i <= n; i++
)
          {
             scanf(
"%d %d %d",&x,&y,&
v);
             cap[x][y] 
+=
 v;
          }
          
          s 
= 1; t =
 m;
          printf(
"%d\n"
,max_flow());
    }
    
return 0
;
}



Dinic 的最大流代码:

#include
<iostream>
#include 
<cstdio>
#include 
<memory.h>
using namespace std;
/************Dinic**********************/

#define Max 210
int flow[Max][Max],d[Max]; //flow is the network
int sta,end,N; //sta is the sourse ,end is the end,N is the number of vector

bool bfs(int s)
{
       
int front=0,rear=0

       
int
 q[Max];
       memset(d,
-1,sizeof(d));  //d[] is the deep

       q[rear++]=s;  d[s]=0;
       
while(front<
rear)
       {
               
int k=q[front++
];
               
for(int i=0;i<=N;i++
)
                  
if(flow[k][i]>0&&d[i]==-1
){
                     d[i]
=d[k]+1
;
                     q[rear
++]=
i;
                  }
       }
       
if(d[end]>=0)   return true
;
       
return false
;
}

int dinic(int k,int sum)  //k is the sourse

{
      
if (k==end)    return
 sum;
      
int os =
 sum;
      
for(int i=0;i<=N&&sum;i++
)
        
if(d[i]==d[k]+1&&flow[k][i]>0
)
        {
                
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end.

                flow[k][i]-=a;
                flow[i][k]
+=
a;
                sum 
-=
 a;
        }
      
return os-
sum;
}
                         
/*******************************************/

int main()
{
    
int
 n,x,y,v;
    
while (scanf("%d %d",&n,&N) !=
 EOF)
    {
          memset(flow,
0,sizeof
(flow));
          
for (int i = 1; i <= n; i++
)
          {
              scanf(
"%d %d %d",&x,&y,&
v);
              flow[x][y] 
+=
 v;
          }
/**********************/

         
int ret=0;
         sta 
= 1; end =
 N;

         
while
(bfs(sta))
             ret 
+= dinic(sta,0x7ffffff
);
                  
/***************************/

         printf(
"%d\n",ret); 
    } 
    
    
return 0
;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理