图论算法----网络流-白红宇

图论算法----网络流

阅读量：7065 次

发布时间：2019-06-28

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

模板：

最大流：

普通增广：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define maxn 1010 8 #define INF 0x3f3f3f3f 9 using namespace std;10 struct edge{11 int to,cap,rev;12 };13 vector
            
             G[maxn];14 bool used[maxn];15 void addedge(int from,int to,int cap){16 G[from].push_back((edge){to,cap,G[to].size()});17 G[to].push_back((edge){ from,0,G[from].size()-1});18 }19 int dfs(int v,int t,int f){20 if (v==t)return f;21 used[v]=true;22 for (int i=0;i
             
              0){25 int d = dfs(e.to,t,min(f,e.cap));26 if (d>0){27 e.cap-=d;28 G[e.to][e.rev].cap +=d;29 return d;30 }31 }32 }33 return 0;34 }35 int max_flow(int s,int t){36 int flow = 0;37 while(1){38 memset(used,0,sizeof(used));39 int f = dfs(s,t,INF);40 if(f==0)return flow;41 flow+=f;42 }43 }44 int main (){45 46 47 }

View Code

Dinic：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                12 #define maxn 20000113 #define INF 0x3f3f3f3f14 using namespace std;15 struct edge{16 int to,cap,rev;17 };18 vector
                 
                  G[maxn];19 void addedge(int from,int to,int cap){20 G[from].push_back((edge){to,cap,G[to].size()});21 G[to].push_back((edge){ from,0,G[from].size()-1});22 }23 int level[maxn];//点的深度24 int iter[maxn];//当前遍历到的边的下标25 void bfs(int s){26 memset(level,-1,sizeof(level));27 queue
                  
                   q;28 level[s]=0;29 q.push(s);30 while(!q.empty()){31 int v = q.front();32 q.pop();33 for (int i=0;i
                   
                    0&&level[e.to]<0){36 level[e.to]=level[v]+1;37 q.push(e.to);38 }39 }40 }41 }42 int dfs(int v,int t,int f){43 if (v==t)return f;44 for (int &i =iter[v];i
                    
                     0&&level[v]
                     
                      0){49 e.cap-=d;50 G[e.to][e.rev].cap += d;51 return d;52 }53 }54 }55 return 0;56 }57 int max_flow(int s,int t){58 int flow = 0;59 while(1){60 bfs(s);61 if(level[t]<0)return flow;62 memset(iter,0,sizeof(iter));63 int f ;64 while((f=dfs(s,t,INF))>0){65 flow+=f;66 }67 }68 }69 int N,M;70 int A[maxn],B[maxn];71 int a[maxn],b[maxn],w[maxn];72 void solve(){73 int s = N,t= s+1;74 for(int i=0;i

View Code

SAP：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #include
               
                 11 #include
                 12 #define maxn 200001 13 #define maxm 1800000 14 #define INF 0x3f3f3f3f 15 using namespace std; 16 const int inf=(1<<29); 17 struct EDGE{ 18 int v,next; 19 int cap; 20 }ee[maxm]; 21 int head[maxn],gap[maxn]; //dep[maxn]; 22 int n,m,src,des,siz;//src=start,des=end; 23 void init(){ 24 siz=0; 25 memset(head,-1,sizeof head); 26 } 27 void addedge(int u,int v,int cap){ 28 ee[siz].v=v,ee[siz].cap=cap; 29 ee[siz].next=head[u]; 30 head[u]=siz++; 31 32 ee[siz].v=u,ee[siz].cap=0; 33 ee[siz].next=head[v]; 34 head[v]=siz++; 35 } 36 int dis[maxn],pre[maxn]; 37 int cur[maxn],aug[maxn]; 38 39 int SAP(int s, int e, int n) 40 { 41 int max_flow = 0, v, u = s; 42 int id, mindis; 43 aug[s] = inf; 44 pre[s] = -1; 45 memset(dis, 0, sizeof(dis)); 46 memset(gap, 0, sizeof(gap)); 47 gap[0] = n; 48 for (int i = 0; i <= n; ++i){ //初始化当前弧为第一条弧 49 cur[i] = head[i]; 50 } 51 52 while (dis[s] < n) 53 { 54 bool flag = false; 55 if (u == e) 56 { 57 max_flow += aug[e]; 58 for (v = pre[e]; v != -1; v = pre[v])//路径回溯更新残留网络 59 { 60 id = cur[v]; 61 ee[id].cap -= aug[e]; 62 ee[id^1].cap += aug[e]; 63 aug[v] -= aug[e]; //修改可增广量，以后会用到 64 if (ee[id].cap == 0) u = v; //不回退到源点，仅回退到容量为0的弧的弧尾 65 } 66 } 67 for (id = cur[u]; id != -1; id = ee[id].next) 68 { // 从当前弧开始查找允许弧 69 v = ee[id].v; 70 if (ee[id].cap > 0 && dis[u] == dis[v] + 1) //找到允许弧 71 { 72 flag = true; 73 pre[v] = u; 74 cur[u] = id; 75 aug[v] = min(aug[u], ee[id].cap); 76 u = v; 77 break; 78 } 79 } 80 if (flag == false) 81 { 82 if (--gap[dis[u]] == 0) break; /*gap优化层次树出现断层则结束算法*/ 83 mindis = n; 84 cur[u] = head[u]; 85 for (id = head[u]; id != -1; id = ee[id].next) 86 { 87 v = ee[id].v; 88 if (ee[id].cap > 0 && dis[v] < mindis) 89 { 90 mindis = dis[v]; 91 cur[u] = id; //修改标号的同时修改当前弧 92 } 93 } 94 dis[u] = mindis + 1; 95 gap[dis[u]]++; 96 if (u != s) u = pre[u]; //回溯继续寻找允许弧 97 } 98 } 99 return max_flow;100 }101 int N,M;102 int A[maxn],B[maxn];103 int a[maxn],b[maxn],w[maxn];104 void solve(){105 int s = N,t= s+1;106 for(int i=0;i

View Code

最小费用流：

bellman-ford：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define maxn 1010 8 #define maxm 1010 9 #define INF 0x3f3f3f3f10 using namespace std;11 struct edge{ int to,cap,cost,rev;};12 int V; //顶点数13 vector
            
              G[maxn];//邻接表14 int dist[maxn];//最短距离15 int prevv[maxn],preve[maxn];//最短路中前驱节点以及对应的边16 void addedge(int from ,int to, int cap, int cost){17 G[from].push_back((edge){to,cap,cost,G[to].size()});18 G[to].push_back((edge){ from,0,-cost,G[from].size()-1});19 }20 21 //求从s到t的流量为f的最小费用流,22 //如果无法增广返回-123 //复杂度：O(F|V||E|)24 int min_cost_flow(int s, int t,int f){25 int res = 0;26 while(f>0){27 //利用bellman-ford求解最短路28 fill (dist,dist+V,INF);29 dist[s]=0;30 bool update = true;31 while(update){32 update = false;33 for(int v = 0; v
             
              0&&dist[e.to]>dist[v]+e.cost){38 dist[e.to]=dist[v]+e.cost;39 prevv[e.to]=v;40 preve[e.to]=i;41 update = true;42 }43 }44 }45 }46 if (dist[t]==INF){47 //无法再增广48 return -1;49 }50 51 //沿着最短路尽量增广52 int d = f;53 for(int v = t; v!=s;v = prevv[v]){54 d = min(d,G[prevv[v]][preve[v]].cap);55 }56 f-=d;57 res+=d*dist[t];58 for(int v = t;v!=s;v = prevv[v]){59 edge &e = G[prevv[v]][preve[v]];60 e.cap -=d;61 G[v][e.rev].cap+=d;62 }63 }64 return res;65 }66 int main (){67 int n,m;68 while(scanf("%d%d",&n,&m)!=EOF){69 V=n+1;70 for(int i=0;i

View Code

Dijkstra：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define maxn 1010 8 #define maxm 1010 9 #define INF 0x3f3f3f3f10 using namespace std;11 typedef pair
            
             P;//first 为最短距离，second为顶点编号12 struct edge{ int to,cap,cost,rev; };13 int V; //顶点数14 vector
             
               G[maxn];//邻接表15 int dist[maxn];//最短距离16 int h[maxn];//顶点的势17 int prevv[maxn],preve[maxn];//最短路中前驱节点以及对应的边18 void addedge(int from ,int to, int cap, int cost){19 G[from].push_back((edge){to,cap,cost,G[to].size()});20 G[to].push_back((edge){ from,0,-cost,G[from].size()-1});21 }22 23 //求从s到t的流量为f的最小费用流,24 //如果无法增广返回-125 //复杂度：O(F|V||E|)26 int min_cost_flow(int s, int t,int f){27 int res = 0;28 fill(h,h+V,0);29 while(f>0){30 //利用Dijkstra更新h31 priority_queue
              
               ,greater
                >q;32 fill (dist,dist+V,INF);33 dist[s]=0;34 q.push(P(0,s));35 while(!q.empty()){36 P p = q.top();37 q.pop();38 int v = p.second;39 if (dist[v]
                
                 0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){43 dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];44 prevv[e.to]=v;45 preve[e.to]=i;46 q.push(P(dist[e.to],e.to));47 }48 }49 }50 if (dist[t]==INF){51 //无法再增广52 return -1;53 }54 for (int v=0;v