网络流

淡淡的烟草味﹌ 2021-11-02 14:26 380阅读 0赞

求最大流后判断下那些边的容量为0即可。。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<vector>
    #include<string>
    #include<math.h>
    #include<map>
    #include<set>
    #include<algorithm>
    using namespace std;
    #define MAXN 2000000
    struct Edge
    {
      int v, next, val;
      Edge( ) { }
      Edge( int V, int N, int Val): v(V), next(N), val(Val) {}             
    }edge[MAXN];
    
    int head[MAXN],size, flow, visit, sum, N, M, ans;
    int gap[MAXN], h[MAXN];
    int path[2000010],vsize;
    int answer[2000010];
    int S,T, vs;
    
    
    void init( )
    {
      for( int i = 0; i < MAXN; i++)
      {
          head[i] = -1;        
           
      }     
      size = 0;
      vsize = 0;
         
    }
    
    
    void AddEdge( int u, int v, int val)
    {
       edge[size] = Edge(v, head[u], val);
       head[u]  = size++;
       
       edge[size] = Edge(u, head[v], val);
       head[v] = size++;
         
    }
    
    
    int dfs( int x, int flow = 0x7f7f7f7f)
    {
       if( x == T )
       {
          return flow;    
       }
       int v, u, high = N, f, tf = 0;
       for( v = head[x]; v != -1; v = edge[v].next )
       {
          u = edge[v].v;
          if( edge[v].val > 0 )
          {
            if( h[x] == h[u] + 1 && (f = dfs(u, min(flow - tf, edge[v].val))))
            { 
              edge[v].val -= f;
              edge[v^1].val += f;
              path[u] = x;
              tf += f;
              if( h[S] >= N || tf == flow)
                return tf;       
            }
            high = min(high, h[u]);
          }   
            
       }
       if( tf  == 0 )
       {
          gap[h[x]]--;
          if( gap[h[x]] == 0 )
             h[S] = N;
          h[x] = high + 1; 
          gap[h[x]]++;     
       }
       return tf;    
    }
    
    void solve( )
    {
       gap[0] = N;
       memset(h, 0, sizeof(h));
       sum = 0;
       while( h[S] < N )
       {
          sum += dfs( S );
       }
       vsize = 0;
       for( int i = 0; i < size; i++)
       {
         int val = edge[i].val;
         if( val == 0 )
         {
            path[vsize++] = i / 2 + 1;
            
         }   
        
       }
       vsize = unique(path, path + vsize) - path;
       printf("%d\n",vsize);
       for( int i = 0; i < vsize; i++)
       {   
           printf("%d\n",path[i]);
       }
       
    }
    
    
    int main( )
    {
       int a, b, c;
       ans = 0;
       while( scanf("%d%d%d%d",&N,&M,&S,&T) != EOF )
       {
         init( );
         memset(answer,0,sizeof(answer));
         for( int i = 1; i <= M; i++)
         {
           scanf("%d%d%d",&a, &b, &c);
           AddEdge(a, b, c);
         
         }
         solve( );
       } 
       return 0; 
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/08/05/2624206.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/b677c5b2399a48189485b249d3389a25.png