lib/Documentation/docs-sonyckson/EK2.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 224
   9 #define MM 500000
  10 #define INF 2100004
  11 /* EDMONDS KARP para grafos dispersos... V  ~<< E. */
  12 typedef struct{
  13     int from, to, cap, flow;
  14 }s_ar;
  15 s_ar aristas[2*MM];
  16 vector<int> vec[NN];
  17 vector<int> ind[NN];
  18 // Siempre hay que inicializar esta variable:
  19 int indice = 0;
  20 void addEdge(int from, int to, int cap, int flow){
  21         for(int i = 0 ;i < vec[from].size() ; i ++ )if( vec[from][i] == to ){
  22                 aristas[ind[from][i]].cap = cap; return;
  23         }
  24         vec[from].push_back(to), ind[from].push_back(indice);
  25         aristas[indice].from = from, aristas[indice].to = to;
  26         aristas[indice].cap = cap, aristas[indice++].flow = 0;
  27         vec[to].push_back(from), ind[to].push_back(indice);
  28         aristas[indice].from = to, aristas[indice].to = from;
  29         aristas[indice].cap = 0, aristas[indice++].flow = 0;
  30 }
  31 int prev[NN];
  32 int q[NN+1];
  33 bool isPath(int s, int t){
  34         memset(prev, -1, sizeof(prev));
  35         int qb, qe; qb = qe = 0;
  36         prev[q[qe++] = s ] = -2;
  37         while( qb < qe && prev[t] == -1 ){
  38                 for(int u = q[qb++], i=0, v; i < vec[u].size(); i++){
  39                         if( prev[v = vec[u][i]] != -1 ) continue;
  40                         if( aristas[ind[u][i]].flow < aristas[ind[u][i]].cap ) prev[q[qe++]=v] = u;
  41                         else if( aristas[ind[u][i]+(ind[u][i]&1?-1:1)].flow ) prev[q[qe++]=v] = u;
  42                 }
  43         }
  44         return prev[t] != -1;
  45 }
  46 int r(int v, int u){
  47         for(int i =0 ;i < vec[v].size() ; i++ )if( vec[v][i] == u ){
  48                 if( aristas[ind[v][i]].cap > aristas[ind[v][i]].flow ){
  49                         return aristas[ind[v][i]].cap-aristas[ind[v][i]].flow;
  50                 }
  51                 return aristas[ind[v][i]+(ind[v][i]&1?-1:1)].flow;
  52                 }
  53 }
  54 void modify(int v, int u, int flow){
  55         for(int i = 0; i < vec[v].size() ; i++) if( vec[v][i] == u ){
  56                 if( aristas[ind[v][i]].cap > aristas[ind[v][i]].flow ){
  57                         aristas[ind[v][i]].flow += flow;
  58                 }else aristas[ind[v][i]+(ind[v][i]&1?-1:1)].flow -= flow;
  59                 return;
  60         }
  61 }
  62 int augment(int s,int t){
  63         int flow = INT_MAX;
  64         prev[s] = s;
  65         for(int u = t, v = prev[u]; v != u; u = v, v = prev[u]) flow = min( flow, r(v,u));
  66         for(int u = t, v = prev[u]; v != u; u = v, v = prev[u]){
  67                  modify(v,u,flow);
  68         }
  69         return flow;
  70 }
  71 int edmondsKarp2(int s, int t){
  72         int flow = 0;
  73         while( isPath(s,t) )flow += augment(s,t);
  74         return flow;
  75 }
  76
  77 int main(){
  78         int i,j ,k;
  79         int N, M;
  80         while(scanf("%i", &N)!=EOF){
  81                 for(i=0;i<220;i++) vec[i].clear(), ind[i].clear();
  82                 indice = 0;
  83                 for(i=0;i<N;i++){
  84                         scanf("%i", &k);
  85                         addEdge(i+1, i+1+N,k,0);
  86                 }
  87                 scanf("%i", &M);
  88                 int a, b, c;
  89                 for(i=0;i<M;i++){
  90                         scanf("%i %i %i", &a, &b, &c);
  91                         addEdge(a+N,b,c,0);
  92                 }
  93                 int B, D;
  94                 scanf("%i %i", &B, &D);
  95                 for(i=0;i<B;i++){
  96                         scanf("%i", &c);
  97                         addEdge(0,c,INF,0);
  98                 }
  99                 for(i=0;i<D;i++){
 100                         scanf("%i", &c);
 101                         addEdge(N+c,2*N+1,INF,0);
 102                 }
 103 //              printf("%i\n", indice);
 104                 int flow = edmondsKarp2(0,2*N+1);
 105                 printf("%i\n", flow);
 106         }return 0;
 107 }