Advertisement
Guest User

Untitled

a guest
Mar 30th, 2017
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.74 KB | None | 0 0
  1. int main()
  2. {
  3.     int n;
  4.  
  5.     cin >> n;
  6.  
  7.     vector<int> sr(n);
  8.     vector<int> sc(n);
  9.  
  10.     for (int i = 0; i < n; ++i)
  11.     {
  12.         cin >> sr[i];
  13.     }
  14.  
  15.     for (int i = 0; i < n; ++i)
  16.     {
  17.         cin >> sc[i];
  18.     }
  19.  
  20.     int s = 0;
  21.     int t = 2 * n + 1;
  22.  
  23.     AdjacencyMatrix network(2 * n + 2);
  24.  
  25.     for (int i = 0; i < network.size(); ++i)
  26.     {
  27.         network[i].resize(network.size(), Edge::empty());
  28.     }
  29.  
  30.     for (int i = 0; i < sc.size(); ++i)
  31.     {
  32.         network[s][i + 1] = Edge(sc[i], 0);
  33.  
  34.         for (int j = 0; j < sr.size(); ++j)
  35.         {
  36.             network[i + 1][1 + n + j] = Edge(100, 0);
  37.         }
  38.     }
  39.  
  40.     for (int i = 0; i < sr.size(); ++i)
  41.     {
  42.         network[1 + n + i][t] = Edge(sr[i], 0);
  43.     }
  44.  
  45.     dinic(network, s, t);
  46.  
  47.     vector<vector<int>> result(n);
  48.  
  49.     for (int i = 0; i < n; ++i)
  50.     {
  51.         result[i].resize(n, 0);
  52.     }
  53.  
  54.     for (int i = s + 1; i < s + n + 1; ++i)
  55.     {
  56.         for (int j = s + n + 1; j < t; ++j)
  57.         {
  58.             if (network[i][j].flow != 0)
  59.             {
  60.                 result[j - 1 - n][i - 1] = network[i][j].flow;
  61.             }
  62.         }
  63.     }
  64.  
  65.     for (int i = 0; i < n; ++i)
  66.     {
  67.         int rowSum = 0;
  68.         int columnSum = 0;
  69.  
  70.         for (int j = 0; j < n; ++j)
  71.         {
  72.             rowSum += result[i][j];
  73.             columnSum += result[j][i];
  74.         }
  75.  
  76.         if (rowSum != sr[i] || columnSum != sc[i])
  77.         {
  78.             cout << "NO";
  79.             return 0;
  80.         }
  81.     }
  82.  
  83.     cout << "YES" << endl;
  84.  
  85.     for (int i = 0; i < n; ++i)
  86.     {
  87.         for (int j = 0; j < n; ++j)
  88.         {
  89.             cout << result[i][j] << ' ';
  90.         }
  91.  
  92.         cout << endl;
  93.     }
  94.  
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement