sup-extra 网络流及其进阶

Posted at 2019-01-28 ICPC 

网络流及其进阶的部分感想

---

​ 　　网络流：将网络看成一堆管道，其中一个点是入水口，一个点是出水口，这样的一种思想。同时也有诸多变形。

​ 　　具有的性质：除了起点与终点之外，每个点的入流量和出流量是相等的。

###可以解决的问题：

1. 最大流问题：最大的情况下能有多少流量。

   具体算法：Dinic算法：

   1、初始化网络和网络流：对每条有向边构造一条带正权值的边和一条权值为0的反向边。建图也可以常规用vector 建。

   2、构造剩余网络和层次网络，若汇点不在层次网络中则算法结束：利用BFS来给每个点标层数，如果汇点没有层数（-1)就说明汇点不在层次网络中了。

   3、在层次图G_L内用一次DFS过程进行增广，每次增广完毕，在层次网络中要去掉因改进流量而导致饱和的弧，DFS执行完毕则该阶段增广完毕：每次去掉的必定是DFS经过的一条链上最小的权值，利用DFS回退来实现对路径上的修改。

   4、转步骤2。

   时间复杂度：O(V^2·E)

   模板题：POJ - 1273

   AC代码：

   #include <cstdio>
   #include <iostream>
   #include <algorithm>
   #include <cstring>
   #include <vector>
   #include <map>
   #include <queue>
   using namespace std;
   const int maxn=202;
   const int INF=0x3f3f3f3f;
   struct edge
   {
       int to,val,nxt;
   }e[maxn*2] ;
   int deep[maxn],son[maxn],n,m,coun,s,t;
   void addedge(int u,int v,int c)
   {
       e[coun].to=v;e[coun].val=c,e[coun].nxt=son[u];
       son[u]=coun++;
   }
   int bfs()
   {
       memset(deep,-1,sizeof(deep));
       queue<int> q;
       deep[s]=0;
       q.push(s);
       while(!q.empty())
       {
           int u=q.front();
           q.pop();
           for(int i=son[u];i!=-1;i=e[i].nxt)
           {
               int v=e[i].to;
               if(deep[v]==-1&&e[i].val>0)
               {
                   deep[v]=deep[u]+1;
                   q.push(v);
               }
           }
       }
       return (deep[t]!=-1);
   }
   int dfs(int u,int val)
   {
       if(u==t)
           return val;
       int res=0;
       for(int i=son[u];i!=-1;i=e[i].nxt)
       {
           int v=e[i].to;
           if(e[i].val&&deep[u]+1==deep[v])
           {
               int tmp=dfs(e[i].to,min(val,e[i].val));
               res+=tmp;
               val-=tmp;
               e[i].val-=tmp;
               e[i^1].val+=tmp;
               if(val==0) break;
           }
       }
       return res;
   }
   int maxflow()
   {
       int res=0;
       while(bfs())
       {
           res+=dfs(s,INF);
       }
       return res;
   }
   int main(void)
   {
       int u,v,c;
       while(~scanf("%d%d",&n,&m))
       {
           s=1,t=m;
           memset(son,-1,sizeof(son));
           coun=0;
           for(int i=0;i<n;i++)
           {
               scanf("%d%d%d",&u,&v,&c);
               addedge(u,v,c);
               addedge(v,u,0);
           }
           /*for(int i=0;i<n;i++)
           {
               cout<<e[i].nxt<<' '<<e[i].to<<' '<<e[i].val<<endl;
           }*/
           printf("%d\n",maxflow());
       }
   	return 0;
   }