网络流算法笔记-白红宇

网络流算法笔记

阅读量：5289 次

发布时间：2019-06-14

本文共 7007 字，大约阅读时间需要 23 分钟。

【例题】

1.POJ Drainage Ditches 【最大流EK算法模板】

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define mod(x) ((x)%M)#define pi acos(-1.0)#define rep(i,x,n) for(int i=(x); i<(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 1<<30;const int maxn = 1e3;const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};int dir[2]={-1,1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int s,t,n,m;inline int read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x;}int head[maxn],tot=1;void init(){ ms(head,-1); tot=1;}struct Pre{ int v,edge;//该点的前一个点（从起点过来） 与该点相连的边（靠近起点的）}pre[maxn];struct node{ int v,w,nxt;}e[maxn];void add(int u,int v,int w){ e[++tot].v=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot;}int vis[maxn];inline bool bfs(){ queue
                       
                         q; ms(vis,0);ms(pre,-1); vis[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u]; i!=-1; i=e[i].nxt) { int v=e[i].v; if(!vis[v]&&e[i].w) { pre[v].v=u; pre[v].edge=i; if(v==t) return 1; vis[v]=1; q.push(v); } } } return 0;}int ek(){ int ans=0; while(bfs()) { int mi=INF; for(int i=t; i!=s; i=pre[i].v)//每次只能增加增广路上最小的边的权值 { mi = min(mi,e[pre[i].edge].w); } for(int i=t; i!=s; i=pre[i].v) { e[ pre[i].edge ].w -= mi; e[ pre[i].edge^1 ].w += mi; } ans += mi; } return ans;}int main(){ while(~scanf("%d%d",&m,&n)) { init(); s=1,t=n; int u,v,w; for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),add(u,v,w),add(v,u,0); printf("%d\n",ek()); }}/*【题意】【类型】最大流EK算法模板【分析】https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-di-zong-jie【时间复杂度&&优化】O(nm^2)(n为点数，m为边数)【trick】【数据】*/

2.洛谷 P3376 【模板】网络最大流

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define mod(x) ((x)%M)#define pi acos(-1.0)#define rep(i,x,n) for(int i=(x); i<(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 1<<30;const int maxn = 5e5+10;const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};int dir[2]={-1,1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int s,t,n,m;inline int read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x;}int head[maxn],tot=1;void init(){ ms(head,-1); tot=1;}struct Pre{ int v,edge;//该点的前一个点（从起点过来） 与该点相连的边（靠近起点的）}pre[maxn];struct node{ int v,w,nxt;}e[maxn];void add(int u,int v,int w){ e[++tot].v=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot;}int inque[maxn];inline bool bfs(){ queue
                       
                         q; ms(inque,0);ms(pre,-1); inque[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u]; i!=-1; i=e[i].nxt) { int v=e[i].v; if(!inque[v]&&e[i].w) { pre[v].v=u; pre[v].edge=i; if(v==t) return 1; inque[v]=1; q.push(v); } } } return 0;}int ek(){ int ans=0; while(bfs()) { int mi=INF; for(int i=t; i!=s; i=pre[i].v)//每次只能增加增广路上最小的边的权值 { mi = min(mi,e[pre[i].edge].w); } for(int i=t; i!=s; i=pre[i].v) { e[ pre[i].edge ].w -= mi; e[ pre[i].edge^1 ].w += mi; } ans += mi; } return ans;}int main(){ init(); n=read(), m=read(), s=read(), t=read(); int u,v,w; for(int i=1;i<=m;i++) u=read(),v=read(),w=read(),add(u,v,w),add(v,u,0); printf("%d\n",ek());}/*4 5 4 34 2 304 3 202 3 202 1 301 3 40【题意】【类型】【分析】【时间复杂度&&优化】【trick】【数据】*/

3.HDU 3549 Flow Problem

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define mod(x) ((x)%M)#define pi acos(-1.0)#define rep(i,x,n) for(int i=(x); i<(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 1<<30;const int maxn = 2e3+3;const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};int dir[2]={-1,1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int s,t,n,m;inline int read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x;}int head[maxn],tot=1;void init(){ ms(head,-1); tot=1;}struct Pre{ int v,edge;//该点的前一个点（从起点过来） 与该点相连的边（靠近起点的）}pre[maxn];struct node{ int v,w,nxt;}e[maxn];void add(int u,int v,int w){ e[++tot].v=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot;}int vis[maxn];inline bool bfs(){ queue
                       
                         q; ms(vis,0);ms(pre,-1); vis[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); if(u==t) return 1; for(int i=head[u]; i!=-1; i=e[i].nxt) { int v=e[i].v; if(!vis[v]&&e[i].w) { pre[v].v=u; pre[v].edge=i; vis[v]=1; q.push(v); } } } return 0;}int ek(){ int ans=0; while(bfs()) { int mi=INF; for(int i=t; i!=s; i=pre[i].v)//每次只能增加增广路上最小的边的权值 { mi = min(mi,e[pre[i].edge].w); } for(int i=t; i!=s; i=pre[i].v) { e[ pre[i].edge ].w -= mi; e[ pre[i].edge^1 ].w += mi; } ans += mi; } return ans;}int main(){ int T,ca=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); init(); s=1,t=n; int u,v,w; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,0); } printf("Case %d: %d\n",ca++,ek()); }}/*【题意】【类型】最大流EK算法模板【分析】【时间复杂度&&优化】O(nm^2)(n为点数，m为边数)【trick】【数据】*/