aydarbiktimirov

Untitled

Jan 25th, 2012
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <climits>
  4.  
  5. int main()
  6. {
  7.     int n, m, sum1 = 0, sum2 = 0;
  8.     std::cin >> n >> m;
  9.     std::vector<std::vector<int> > c(n + m + 2, std::vector<int>(n + m + 2, 0));
  10.     for (int i = 0; i < n; ++i)
  11.     {
  12.         int tmp;
  13.         std::cin >> tmp;
  14.         c[0][i + 1] = tmp;
  15.         sum1 += tmp;
  16.         for (int j = 0; j < m; ++j)
  17.         {
  18.             c[i + 1][n + j + 1] = 1;
  19.         }
  20.     }
  21.     for (int j = 0; j < m; ++j)
  22.     {
  23.         int tmp;
  24.         std::cin >> tmp;
  25.         c[n + j + 1][n + m + 1] = tmp;
  26.         sum2 += tmp;
  27.     }
  28.  
  29.     if (sum1 != sum2)
  30.     {
  31.         std::cout << "impossible" << std::endl;
  32.         return 0;
  33.     }
  34.  
  35.     std::vector<std::vector<int> > f(c.size(), std::vector<int>(c.size()));
  36.     for (; ; )
  37.     {
  38.         std::vector<int> from(c.size(), -1);
  39.         std::vector<int> q(c.size());
  40.         int h = 0, t = 0;
  41.         q[t++] = 0;
  42.         from[0] = 0;
  43.         for (int cur; h < t; )
  44.         {
  45.             cur = q[h++];
  46.             for (int v = 0; v < (int)c.size(); ++v)
  47.             {
  48.                 if (from[v] == -1 && c[cur][v] - f[cur][v] > 0)
  49.                 {
  50.                     q[t++] = v;
  51.                     from[v] = cur;
  52.                 }
  53.             }
  54.         }
  55.         if (from[c.size() - 1] == -1)
  56.         {
  57.             break;
  58.         }
  59.         int cf = INT_MAX;
  60.         for (int cur = c.size() - 1; cur != 0; )
  61.         {
  62.             int prev = from[cur];
  63.             cf = std::min(cf, c[prev][cur] - f[prev][cur]);
  64.             cur = prev;
  65.         }
  66.         for (int cur = c.size() - 1; cur != 0; )
  67.         {
  68.             int prev = from[cur];
  69.             f[prev][cur] += cf;
  70.             f[cur][prev] -= cf;
  71.             cur = prev;
  72.         }
  73.     }
  74.  
  75.     int flow = 0;
  76.     for (int i = 0; i < (int)c.size(); ++i)
  77.     {
  78.         if (c[0][i])
  79.         {
  80.             flow += f[0][i];
  81.         }
  82.     }
  83.     if (flow != sum1)
  84.     {
  85.         std::cout << "impossible" << std::endl;
  86.     }
  87.     else
  88.     {
  89.         for (int i = 0; i < n; ++i)
  90.         {
  91.             for (int j = 0; j < m; ++j)
  92.             {
  93.                 std::cout << f[i + 1][n + j + 1];
  94.             }
  95.             std::cout << std::endl;
  96.         }
  97.     }
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment