fork(1) download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <queue>
  6. #include <cstring>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. int n, p, sz, A[55], vis[1005], B[52][52], adj[1005][1005];
  12.  
  13. bool bfs()
  14. {
  15.     queue < int > q;
  16.     memset(vis, -1, sizeof(vis));
  17.     q.push(0);
  18.     vis[0] = 0;
  19.     bool ok = false;
  20.     while(!q.empty())
  21.     {
  22.         int temp = q.front();       q.pop();
  23.  
  24.         for(int i = 0;i < sz;++i)
  25.         {
  26.             if(vis[i] == -1 and adj[temp][i] > 0)
  27.             {
  28.                 vis[i] = temp;
  29.                 q.push(i);
  30.                 if(i == sz - 1)
  31.                 {
  32.                     ok = true;
  33.                     break;
  34.                 }
  35.             }
  36.         }
  37.     }
  38.     if(!ok)         return false;
  39.  
  40.     int temp = sz - 1;
  41.     while(vis[temp] != temp)
  42.     {
  43.         int prev = vis[temp];
  44.         adj[prev][temp] -= 1;
  45.         adj[temp][prev] += 1;
  46.         temp = prev;
  47.     }
  48.     return true;
  49. }
  50.  
  51. int main()
  52. {
  53. //    freopen("B-large-practice.in", "r", stdin);
  54. //    freopen("out.out", "w", stdout);
  55.  
  56.     int t, c = 0;
  57.     scanf("%d", &t);
  58.     while(t--)
  59.     {
  60.         ++c;
  61.         scanf("%d%d", &n, &p);
  62.         sz = n * p + 2;
  63.  
  64.         for(int i = 0;i < n;++i)
  65.             scanf("%d", A + i);
  66.  
  67.         for(int i = 0;i < n;++i)
  68.             for(int j = 0;j < p;++j)
  69.                 scanf("%d", &B[i][j]);
  70.  
  71.  
  72.         ///from src
  73.         for(int i = 0;i < p;++i)
  74.         {
  75.             int t = B[0][i];
  76.             int ma = floor(t * 10.0 / (A[0] * 9.0));
  77.             int mi = ceil(t * 10.0 / (A[0] * 11.0));
  78.  
  79.             if(mi <= ma)
  80.                 adj[0][i + 1] = 1;
  81.         }
  82.  
  83.         ///between packages
  84.         for(int i = 0;i < n - 1;++i)
  85.         {
  86.             for(int j = 0;j < p;++j)
  87.             {
  88.                 int t1 = B[i][j];
  89.                 int ma1 = floor(t1 * 10.0 / (A[i] * 9.0));
  90.                 int mi1 = ceil(t1 * 10.0 / (A[i] * 11.0));
  91.  
  92.                 for(int k = 0;k < p;++k)
  93.                 {
  94.                     int t2 = B[i + 1][k];
  95.                     int ma2 = floor(t2 * 10.0 / (A[i + 1] * 9.0));
  96.                     int mi2 = ceil(t2 * 10.0 / (A[i + 1] * 11.0));
  97.  
  98.                     if(mi1 <= ma1 and mi2 <= ma2 and ((mi2 >= mi1 and mi2 <= ma1) or (ma2 >= mi1 and ma2 <= ma1)))
  99.                         adj[p * i + j + 1][p * (i + 1) + k + 1] = 1;
  100.                 }
  101.             }
  102.         }
  103.  
  104.         ///to dest
  105.         for(int i = 0;i < p;++i)
  106.         {
  107.             int t = B[n - 1][i];
  108.             int ma = floor(t * 10.0 / (A[n - 1] * 9.0));
  109.             int mi = ceil(t * 10.0 / (A[n - 1] * 11.0));
  110.  
  111.             if(mi <= ma)
  112.                 adj[p * (n - 1) + i + 1][sz - 1] = 1;
  113.         }
  114.         int ans = 0;
  115.         while(bfs())
  116.             ++ans;
  117.  
  118.         printf("Case #%d: %d\n", c, ans);
  119.         memset(adj, 0, sizeof(adj));
  120.     }
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0s 19200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eqAerx
language:
C++14 (gcc 8.3)
created:
8 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!