lib/Documentation/docs-sonyckson/dinic.cpp

   1 #include <cstdio>
   2 #include <cstdlib>
   3 #include <iostream>
   4 #include <sstream>
   5 #include <vector>
   6 #include <string>
   7 using namespace std;
   8 #define NN 210
   9 #define MM 500000
  10 #define INF 2100004
  11 int edges[NN][NN*2], deg[NN], cap[NN][NN];
  12 int q[NN], prev[NN];
  13 void addEdge(int from, int to, int C, int flow){
  14         edges[from][deg[from]++] = to;
  15         cap[from][to] = C;
  16         edges[to][deg[to]++] = from;
  17 }
  18 int dinic(int s, int t){
  19         int flow = 0;
  20         while(1){
  21                 memset(prev, -1, sizeof(prev));
  22                 int qb =0, qe =0;
  23                 prev[q[qe++] = s ] = -2;
  24                 while( qb < qe && prev[t] == -1 )
  25                         for(int u = q[qb++], v, i = 0;i<deg[u]; i++ )
  26                                 if( prev[v=edges[u][i]] == -1 && cap[u][v] )prev[q[qe++] = v] = u;
  27
  28                 if( prev[t] == -1 ) break;
  29                 prev[s] = s;
  30                 for(int z = 0; z < t ; z ++ )if( cap[z][t] && prev[z] != -1 ){
  31                         int mf = INT_MAX;
  32                         for(int u = t, v = prev[u]; u != v; u = v, v = prev[u])
  33                                 mf = min ( mf, cap[v][u] );
  34                         if( !mf ) continue;
  35                         for(int u = t, v = prev[u]; u != v; u = v, v = prev[u])
  36                                 cap[v][u] -= mf, cap[u][v] += mf;
  37                         flow += mf;
  38                 }
  39         }return flow;
  40 }
  41 int main(){
  42         int i,j ,k;
  43         int N, M;
  44         while(scanf("%i", &N)!=EOF){
  45                 memset(deg, 0, sizeof(deg));
  46                 memset(cap, 0, sizeof(cap));
  47                 for(i=0;i<N;i++){
  48                         scanf("%i", &k);
  49                         addEdge(i+1, i+1+N,k,0);
  50                 }
  51                 scanf("%i", &M);
  52                 int a, b, c;
  53                 for(i=0;i<M;i++){
  54                         scanf("%i %i %i", &a, &b, &c);
  55                         addEdge(a+N,b,c,0);
  56                 }
  57                 int B, D;
  58                 scanf("%i %i", &B, &D);
  59                 for(i=0;i<B;i++){
  60                         scanf("%i", &c);
  61                         addEdge(0,c,INF,0);
  62                 }
  63                 for(i=0;i<D;i++){
  64                         scanf("%i", &c);
  65                         addEdge(N+c,2*N+1,INF,0);
  66                 }
  67 //              printf("%i\n", indice);
  68                 int flow = dinic(0,2*N+1);
  69                 printf("%i\n", flow);
  70         }return 0;
  71 }