fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. vector<int>G[300] ;
  4. bool vis[300][300] ;
  5. int dist[300][300] ;
  6. int P[300] ;
  7. struct triple {
  8.     int u , v , w ;
  9.     triple() {}
  10.     triple( int _u , int _v , int _w ) {
  11.         u = _u ;
  12.         v = _v ;
  13.         w = _w ;
  14.     }
  15. };
  16. int M ;
  17. int Back_Track(int src,int sink) {
  18.  
  19.     int parent = P[sink] ;
  20.     M = min( M , dist[parent][sink] );
  21.  
  22.     if( parent == src ){
  23.         dist[parent][sink] -= M ;
  24.         dist[sink][parent] += M ;
  25.         return M ;
  26.     }
  27.  
  28.     int ret = Back_Track( src , parent ) ;
  29.  
  30.     dist[parent][sink] -= ret ;
  31.     dist[sink][parent] += ret ;
  32.  
  33.     return M ;
  34. }
  35.  
  36. int Find_Aug_Path(int src, int sink) {
  37.  
  38.     memset( P , 0 , sizeof P ) ;
  39.     queue<int>Q ;
  40.     Q.push( src ) ;
  41.     P[src] = src ;
  42.     while( !Q.empty() ) {
  43.         int nSrc = Q.front() ;
  44.         Q.pop() ;
  45.         int l = G[nSrc].size() ;
  46.         for( int i = 0 ; i < l ; i++ ) {
  47.             int v = G[nSrc][i] ;
  48.             if( P[v] == 0 && dist[nSrc][v] > 0 ) {
  49.                 P[v] = nSrc ;
  50.                 Q.push( v ) ;
  51.                 if( v == sink ) {
  52.                     M = 1 << 30 ;
  53.                     return Back_Track(src,sink) ;
  54.                 }
  55.             }
  56.  
  57.         }
  58.     }
  59.     return 0 ;
  60.  
  61. }
  62.  
  63. int Edmonds_Karp(int src,int sink) {
  64.     int ans = 0 ;
  65.     int tmp = Find_Aug_Path( src , sink ) ;
  66.     ans += tmp ;
  67.     while( tmp ) {
  68.         tmp = Find_Aug_Path( src , sink ) ;
  69.         ans += tmp ;
  70.     }
  71.     return ans ;
  72. }
  73.  
  74. int main() {
  75.  
  76.     int cases , caseno = 1 ;
  77.     scanf("%d",&cases ) ;
  78.     while( cases -- ) {
  79.         int n ;
  80.         scanf("%d",&n) ;
  81.         int temp[n+1] ;
  82.         for( int i = 1 ; i<= n ; i++ ) {
  83.             scanf("%d",&temp[i]) ;
  84.         }
  85.         int e ;
  86.         scanf("%d",&e) ;
  87.         triple T[e] ;
  88.         for( int i = 0 ; i < e ; i++ ) {
  89.             int u , v , w ;
  90.             scanf("%d%d%d",&u,&v,&w) ;
  91.             T[i] = triple( u , v , w );
  92.         }
  93.         int nsrc , nsink ;
  94.         scanf("%d%d",&nsrc,&nsink) ;
  95.  
  96.         set<int> SRC ;
  97.         set<int> SINK ;
  98.  
  99.         for( int i = 0 ; i < nsrc ; i++ ) {
  100.             int tmp ;
  101.             scanf("%d",&tmp) ;
  102.             SRC.insert(tmp) ;
  103.         }
  104.         for( int i = 0 ; i < nsink ; i++ ) {
  105.             int tmp ;
  106.             scanf("%d",&tmp) ;
  107.             SINK.insert(tmp) ;
  108.         }
  109.  
  110.         memset(dist , 0 , sizeof dist ) ;
  111.         memset(vis , 0 , sizeof vis ) ;
  112.         for( set<int>::iterator it = SRC.begin() ; it != SRC.end() ; it++ ) {
  113.             if( vis[0][*it] == 0 ) {
  114.                 G[0].push_back( *it ) ;
  115.                 vis[0][*it] = 1 ;
  116.             }
  117.             dist[0][*it] += temp[*it] ;
  118.         }
  119.         for( set<int>::iterator it = SINK.begin() ; it != SINK.end() ; it++ ) {
  120.             if( vis[*it][250] == 0 ) {
  121.                 G[*it].push_back( 250 ) ;
  122.                 vis[*it][250] = 1 ;
  123.             }
  124.             dist[*it][250] += temp[*it] ;
  125.         }
  126.  
  127.         for( int i = 0 ; i < e ; i++ ) {
  128.             if(SRC.find(T[i].u)==SRC.end() ) {
  129.                 if( vis[T[i].u][T[i].u+120] == 0 ) {
  130.  
  131.                     vis[T[i].u][T[i].u+120] = 1 ;
  132.  
  133.                     G[T[i].u].push_back( T[i].u+120) ;
  134.                     G[T[i].u+120].push_back( T[i].u ) ;
  135.  
  136.                     G[T[i].u+120].push_back( T[i].v ) ;
  137.                     G[T[i].v].push_back( T[i].u+120 ) ;
  138.  
  139.  
  140.                 }
  141.                 dist[T[i].u][T[i].u+120] += temp[T[i].u] ;
  142.                 dist[T[i].u+120][T[i].v] += T[i].w ;
  143.             }else{
  144.                 if( vis[T[i].u][T[i].v] == 0 ){
  145.                     vis[T[i].u][T[i].v] = 1 ;
  146.                     G[T[i].u].push_back( T[i].v ) ;
  147.                     G[T[i].v].push_back( T[i].u ) ;
  148.                 }
  149.                 dist[T[i].u][T[i].v] += T[i].w ;
  150.             }
  151.         }
  152.  
  153.         cout << "Case " << caseno++ << ": " << Edmonds_Karp(0,250) << "\n" ;
  154.         for( int i = 0 ; i < 300 ; i++ )G[i].clear() ;
  155.     }
  156.     return 0 ;
  157. }
  158.  
Success #stdin #stdout 0s 3728KB
comments (?)
stdin
copy 
2

4

10 20 30 40

6

1 2 5

1 3 10

1 4 13

2 3 5

2 4 7

3 4 20

3 1

1 2 3 4

2

50 100

1

1 2 100

1 1

1 2
stdout
copy 
Case 1: 37
Case 2: 50
https://ideone.com/yBO69l
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!