poj1273 Drainage Ditches (最大流板子

网络流一直没学，来学一波网络流。

https://vjudge.net/problem/POJ-1273

题意：给定点数，边数，源点，汇点，每条边容量，求最大流。

解法：EK或dinic。

EK：每次增广用bfs选择一条从源到汇具有最少边数的增广路径，然后找出该路径容量最小的边，就是此次增加的流量，然后沿该路径增加反向边，同时修改每条边的容量，重复上述过程直到找不到增广路（即minFlow = 0)为止。

dinic: 每次bfs从源点到汇点分层（层数是源点到它最少要经过的边数），然后dfs从源点开始不断向下一层找增广路，碰到汇点说明找到一条，进行增广。然后回溯到点u（u是满足（u,v)容量为0的最上层节点）继续寻找增广路，如果回溯到源点且无法继续往下走dfs结束，然后对残余网络再分层，再dfs直到无法分层，算法结束。

 #include<iostream>

 #include<queue>

 #include<cstring>

 using namespace std;

 int G[][];

 int pre[]; //前驱

 bool vis[];

 int n,m; //1是源，m是汇

 inline int solve(){

     deque<int> q;

     memset(pre,,sizeof pre);

     memset(vis,,sizeof vis);

     pre[] = ;

     vis[] = ;

     q.push_back();

     bool find = false;

     while(!q.empty()){

         int v = q.front();

         q.pop_front();

         for(int i=;i<=m;i++){

             if(G[v][i]>&&vis[i]==){

                 pre[i] = v;

                 vis[i] = ;

                 if(i==m){

                     find = true;

                     q.clear();

                     break;

                 }

                 else q.push_back(i);

             }

         }

     }

     if(!find) return ;

     int minFlow = 0x3f3f3f3f;

     int v = m;

     while(pre[v]){

         minFlow = min(minFlow,G[pre[v]][v]);

         v = pre[v];

     }

     v = m;

     while(pre[v]){

         G[pre[v]][v] -= minFlow;

         G[v][pre[v]] += minFlow;

         v = pre[v];

     }

     return minFlow;

 }

 int main(){

     while(cin>>n>>m){

         memset(G,,sizeof G);

         for(int i=;i<n;i++){

             int s,e,c;

             cin>>s>>e>>c;

             G[s][e] += c;

         }

         int maxFlow = ;

         int aug;

         while(aug=solve())

             maxFlow += aug;

         cout<<maxFlow<<endl;

     }

     return ;

 }

 #include<iostream>

 #include<queue>

 #include<cstring>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 int G[][];

 bool vis[];

 int Layer[];

 int n,m; //1是源点，m是汇点

 inline bool countLayer(){

     int layer = ;

     deque<int> q;

     memset(Layer,0xff,sizeof Layer);

     Layer[] = ;

     q.push_back();

     while(!q.empty()){

         int v = q.front();

         q.pop_front();

         for(int j=;j<=m;j++){

             if(G[v][j]>&&Layer[j]==-){

                 Layer[j] = Layer[v]+;

                 if(j==m) return true;

                 else q.push_back(j);

             }

         }

     }

     return false;

 }

 inline int dinic(){

     int maxFlow = ;

     deque<int> q;

     while(countLayer()){

         q.push_back();

         memset(vis,,sizeof vis);

         vis[] = ;

         while(!q.empty()){

             int nd = q.back();

             if(nd==m){

                 int minc = inf;

                 int minc_vs;

                 for(int i=;i<q.size();i++){

                     int vs = q[i-];

                     int ve = q[i];

                     if(G[vs][ve]>){

                         if(minc>G[vs][ve]){

                             minc = G[vs][ve];

                             minc_vs = vs;

                         }

                     }

                 }

                 maxFlow += minc;

                 for(int i=;i<q.size();i++){

                     int vs = q[i-];

                     int ve = q[i];

                     G[vs][ve] -= minc;

                     G[ve][vs] += minc;

                 }

                 while(!q.empty()&&q.back()!=minc_vs){

                     vis[q.back()] = ;

                     q.pop_back();

                 }

             }

             else {

                 int i;

                 for(i=;i<=m;i++){

                     if(G[nd][i]>&&Layer[i]==Layer[nd]+&&!vis[i]){

                         vis[i] = ;

                         q.push_back(i);

                         break;

                     }

                 }

                 if(i>m) q.pop_back();

             }

         }

     }

     return maxFlow;

 }

 int main(){

     while(cin>>n>>m){

         memset(G,,sizeof G);

         for(int i=;i<n;i++){

             int s,e,c;

             cin>>s>>e>>c;

             G[s][e] += c;

         }

         cout<<dinic()<<endl;

     }

     return ;

 }

巴特西

poj1273 Drainage Ditches (最大流板子

最新文章

热门文章