网络流入门-白红宇

网络流入门

阅读量：7050 次

发布时间：2019-06-28

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

poj1459

http://poj.org/problem?id=1459

电站由组成consumer,dispatcher,power station，问最大传输电流

题意故意弄得非常复杂，其实就是多源多汇点，那么只要设置一个s往所有的源连，把所有的汇连到一个t再dinic就行了。

值得注意的两点:1.init必须在所有的开头调用 2.这题的(1,2)20这种读入比较奇葩，只要先读入buf,然后sscanf("(%d,%d)%d")就可以了

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   #include
                    
                     using namespace std;#define For(i,k,n) for(int i=k;i<=n;i++)#define ForD(i,k,n) for(int i=n;i>=k;i--)#define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define NEG(a) memset(a,-1,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define print(b,a) cout<
                     <<"="<<
                       
                        0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; if(rear>=MAXN)rear=0; if(v==end)return 1; } } } return 0;}int dinic(int start,int end){ int res=0; int top; int stack[MAXN];//stack为栈，存储当前增广路 int cur[MAXN];//存储当前点的后继 while(BFS(start,end)) { //printf("res=%d\n",res); memcpy(cur,head,sizeof(head)); int u=start; top=0; while(1) { if(u==end) { int min=INF; int loc; for(int i=0;i
                        
                         edge[stack[i]].cap) { min=edge[stack[i]].cap; loc=i; } for(int i=0;i

View Code

poj1698

http://poj.org/problem?id=1698

alice要拍n部电影，每部电影要至少拍di天，必须要wi天内拍完，给出每个电影能在一个礼拜那些天拍。问能否拍完

s往电影连di,电影往所有能拍的天连1，所有的天往t连1，最大流

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   #include
                    
                     using namespace std;#define For(i,k,n) for(int i=k;i<=n;i++)#define ForD(i,k,n) for(int i=n;i>=k;i--)#define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define NEG(a) memset(a,-1,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define print(b,a) cout<
                     <<"="<<
                       
                        0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; if(rear>=MAXN)rear=0; if(v==end)return 1; } } } return 0;}int dinic(int start,int end){ int res=0; int top; int stack[MAXN]; int cur[MAXN]; while(BFS(start,end)) { memcpy(cur,head,sizeof(head)); int u=start; top=0; while(1) { if(u==end) { int min=INF; int loc; for(int i=0;i
                        
                         edge[stack[i]].cap) { min=edge[stack[i]].cap; loc=i; } for(int i=0;i

View Code

poj2112

http://poj.org/problem?id=2112

有K台挤奶机(编号1~K)，C头奶牛(编号K+1~K+C)，给出各点之间距离。现在要让C头奶牛到挤奶机去挤奶，每台挤奶机只能处理M头奶牛，求使所走路程最远的奶牛的路程最短的方案。

非常简单，二分dinic

值得注意的只是二分的时候r设置大一点

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   #include
                    
                     using namespace std;#define For(i,k,n) for(int i=k;i<=n;i++)#define ForD(i,k,n) for(int i=n;i>=k;i--)#define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define NEG(a) memset(a,-1,sizeof(a));#define FILL(a) memset(a,0x3f,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define print(b,a) cout<
                     <<"="<<
                       
                        0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; if(rear>=MAXN)rear=0; if(v==end)return 1; } } } return 0;}int dinic(int start,int end){ int res=0; int top; int stack[MAXN]; int cur[MAXN]; while(BFS(start,end)) { memcpy(cur,head,sizeof(head)); int u=start; top=0; while(1) { if(u==end) { int min=INF; int loc; for(int i=0;i
                        
                         edge[stack[i]].cap) { min=edge[stack[i]].cap; loc=i; } for(int i=0;i
                         
                          =d[i][j]) addedge(i,j,1); int ret=dinic(0,K+C+1); //printf("ret=%d\n",ret); if(ret==C) { r=m-1; ans=m; } else { l=m+1; } } printf("%d\n",ans); return 0;}

View Code

poj2455

蜜汁无限tle，暂时搁置

转载于:https://www.cnblogs.com/diang/p/5720348.html

你可能感兴趣的文章