lib/Documentation/docs-sonyckson/EK1.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 INF 2100004
  10 typedef struct{
  11         int from, to, cap, flow;
  12 }s_ar;
  13 vector<s_ar> salen[NN], llegan[NN];
  14 void addEdge(int from, int to, int cap, int flow){
  15         s_ar e;
  16         e.from = from, e.to = to, e.cap = cap, e.flow = flow;
  17         salen[from].push_back(e);llegan[to].push_back(e);
  18 }
  19 int prev[NN+1];
  20 int dir[NN+1];
  21 bool isPath(int s, int t){
  22         int i,j ,k;
  23         int q[2*NN];
  24         int qb, qe; qb = qe = 0;
  25         memset(prev, -1, sizeof(prev));
  26         prev[q[qe++] = s ] = -2;
  27         while( qb < qe && prev[t] == -1 ){
  28                 for(int v = q[qb++], i=0, u; i<max(salen[v].size(), llegan[v].size() ); i++){
  29                         if(i < salen[v].size() &&  prev[u = salen[v][i].to] == -1
  30                                         && salen[v][i].flow < salen[v][i].cap ){
  31                                 prev[q[qe++] = u] = v, dir[u] = 1;;
  32                         }
  33                         if(i<llegan[v].size() && prev[u = llegan[v][i].from] == -1
  34                                         && llegan[v][i].flow ){
  35                                 prev[q[qe++] = u] = v, dir[u] = -1;
  36                         }
  37                 }
  38         }
  39         return prev[t] != -1;
  40 }
  41 int r(int u, int v, int d){
  42         if( d == 1 ){
  43                 for(int i = 0; i < salen[u].size();i++)if( salen[u][i].to == v
  44                  && salen[u][i].flow < salen[u][i].cap ){
  45                          return salen[u][i].cap-salen[u][i].flow;
  46                  }
  47         }
  48         for(int i = 0; i < llegan[u].size();i++)if( llegan[u][i].from == v
  49          && llegan[u][i].flow ){
  50                  return llegan[u][i].flow;
  51          }
  52          return 0;
  53 }
  54 void modify(int uu, int vv, int d, int flow){
  55         int u, v;
  56         if( d == 1 ){
  57                 u = uu, v = vv;
  58                 for(int i = 0; i < salen[u].size();i++)if( salen[u][i].to == v
  59                         && salen[u][i].flow < salen[u][i].cap ){
  60                         salen[u][i].flow += flow;
  61                         break;
  62                 }
  63                 swap(u,v);
  64                 for(int i = 0; i < llegan[u].size();i++)if( llegan[u][i].from == v
  65                    && llegan[u][i].flow < llegan[u][i].cap ){
  66                         llegan[u][i].flow += flow;
  67                         return;
  68                 }
  69         }else{
  70                 u = vv, v = uu;
  71                 for(int i = 0; i < salen[u].size();i++)if( salen[u][i].to == v
  72                         && salen[u][i].flow ){
  73                         salen[u][i].flow += flow;
  74                         break;
  75                 }
  76                 swap(u,v);
  77                 for(int i = 0; i < llegan[u].size();i++)if( llegan[u][i].from == v
  78                    && llegan[u][i].flow ){
  79                         llegan[u][i].flow -= flow;
  80                         return;
  81                 }
  82         }
  83 }
  84 int augment(int s, int t){
  85         int flow = INT_MAX;
  86         prev[s] = s;
  87         for(int v = t, u = prev[v]; v != u; v = u, u = prev[v]){
  88                 flow = min(flow, r(u,v,dir[v]));
  89         }
  90         for(int v = t, u = prev[v]; v != u; v = u, u = prev[v]){
  91 //              if( v == t || u == s ) continue;
  92                 modify(u,v,dir[v], flow);
  93         }
  94         return flow;
  95 }
  96 int edmondsKarp(int s,int t){
  97         int res = 0;
  98         while( isPath(s,t) ) res += augment(s,t);
  99         return res;
 100 }
 101
 102 int main(){
 103         int i,j ,k;
 104         int N, M;
 105         while(scanf("%i", &N)!=EOF){
 106                 for(i=0;i<2*N+4;i++) salen[i].clear(), llegan[i].clear();
 107                 for(i=0;i<N;i++){
 108                         scanf("%i", &k);
 109                         addEdge(i+1, i+1+N,k,0);
 110                 }
 111                 scanf("%i", &M);
 112                 int a, b, c;
 113                 for(i=0;i<M;i++){
 114                         scanf("%i %i %i", &a, &b, &c);
 115                         addEdge(a+N,b,c,0);
 116                 }
 117                 int B, D;
 118                 scanf("%i %i", &B, &D);
 119                 for(i=0;i<B;i++){
 120                         scanf("%i", &c);
 121                         addEdge(0,c,INF,0);
 122                 }
 123                 for(i=0;i<D;i++){
 124                         scanf("%i", &c);
 125                         addEdge(N+c,2*N+1,INF,0);
 126                 }
 127                 int flow = edmondsKarp(0,2*N+1);
 128                 printf("%i\n", flow);
 129         }return 0;
 130 }