fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define MAXN 204
  6.  
  7. int h[MAXN], e[MAXN];
  8. int r[MAXN / 2], col[MAXN / 2];
  9. int c[MAXN][MAXN], f[MAXN][MAXN], cf[MAXN][MAXN];
  10. bool visit[MAXN];
  11. vector<int> graph[MAXN];
  12.  
  13. void initializePreflow(int n, int s, int t)
  14. {
  15.     memset(h, 0, (n + 1) * sizeof(int));
  16.     h[s] = n;
  17.     memset(e, 0, (n + 1) * sizeof(int));
  18.     int v;
  19.     for (int i = 0; i < graph[s].size(); i++) {
  20.         v = graph[s][i];
  21.         f[s][v] = c[s][v];
  22.         f[v][s] = -c[s][v];
  23.         e[v] = c[s][v];
  24.         e[s] -= c[s][v];
  25.         cf[s][v] = c[s][v] - f[s][v];
  26.         cf[v][s] = c[v][s] - f[v][s];
  27.     }
  28. }
  29.  
  30. void push(int u, int v)
  31. {
  32.     int temp = min(e[u], cf[u][v]);
  33.     f[u][v] += temp;
  34.     f[v][u] = -f[u][v];
  35.     e[u] -= temp;
  36.     e[v] += temp;
  37.     cf[u][v] = c[u][v] - f[u][v];
  38.     cf[v][u] = c[v][u] - f[v][u];
  39. }
  40.  
  41. void maxflow(int n, int s, int t)
  42. {
  43.     queue<int> q;
  44.     int u, v, m;
  45.  
  46.     initializePreflow(n, s, t);
  47.  
  48.     for (int i = 0; i < graph[s].size(); i++) {
  49.         if (graph[s][i] != t) {
  50.             q.push(graph[s][i]);
  51.             visit[graph[s][i]] = 1;
  52.         }
  53.     }
  54.  
  55.     while (!q.empty()) {
  56.         u = q.front();
  57.         m = -1;
  58.         for (int i = 0; i < graph[u].size() && e[u] > 0; i++) {
  59.             v = graph[u][i];
  60.             if (cf[u][v] > 0) {
  61.                 if (h[u] > h[v]) {
  62.                     push(u, v);
  63.                     if (!visit[v] && v != s && v != t) {
  64.                         visit[v] = true;
  65.                         q.push(v);
  66.                     }
  67.                 }
  68.                 else if (m == -1)
  69.                     m = h[v];
  70.                 else
  71.                     m = min(m, h[v]);
  72.             }
  73.         }
  74.         if (e[u] != 0)
  75.             h[u] = 1 + m;
  76.         else {
  77.             visit[u] = false;
  78.             q.pop();
  79.         }
  80.     }
  81. }
  82.  
  83. int main()
  84. {
  85.     int n, s, t;
  86.     int sr[MAXN / 2], sc[MAXN / 2];
  87.     int A[MAXN / 2][MAXN / 2];
  88.     scanf("%d", &n);
  89.     s = 0;
  90.     t = 2 * n + 1;
  91.  
  92.     for (int i = 1; i <= n; i++) 
  93.         scanf("%d", &sr[i]);
  94.  
  95.     for (int i = 1; i <= n; i++)
  96.         scanf("%d", &sc[i]);
  97.  
  98.     for (int i = 1; i <= n; i++) {
  99.         graph[s].push_back(i);
  100.         graph[i].push_back(s);
  101.         c[s][i] = sc[i];
  102.         cf[s][i] = c[s][i];
  103.     }
  104.  
  105.     for (int i = n + 1; i <= 2 * n; i++) {
  106.         graph[i].push_back(t);
  107.         graph[t].push_back(i);
  108.         c[i][t] = sr[i - n];
  109.         cf[i][t] = c[i][t];
  110.     }
  111.  
  112.     for (int i = 1; i <= n; i++) {
  113.         for (int j = n + 1; j <= 2 * n; j++) {
  114.             graph[i].push_back(j);
  115.             graph[j].push_back(i);
  116.             c[i][j] = 100;
  117.             cf[i][j] = c[i][j];
  118.         }
  119.     }
  120.  
  121.     maxflow(n, s, t);
  122.  
  123.     bool possible = true;
  124.  
  125.     for (int i = 1; i <= n && possible; i++) {
  126.         for (int j = 1; j <= n && possible; j++) {
  127.             A[i][j] = f[j][i + n];
  128.             if (A[i][j] < 0 || A[i][j] > 100)
  129.                 possible = false;
  130.             r[i] += A[i][j];
  131.             col[j] += A[i][j];
  132.         }
  133.     }
  134.  
  135.     if (possible) {
  136.         for (int i = 1; i <= n; i++) {
  137.             if (sr[i] != r[i] || sc[i] != col[i])
  138.                 possible = false;
  139.         }
  140.     }
  141.  
  142.     if (possible) {
  143.         printf("YES\n");
  144.         for (int i = 1; i <= n; i++) {
  145.             for (int j = 1; j <= n; j++) {
  146.                 if (j == 1)
  147.                     printf("%d", A[i][j]);
  148.                 else
  149.                     printf(" %d", A[i][j]);
  150.             }
  151.             printf("\n");
  152.         }
  153.     }
  154.     else
  155.         printf("NO\n");
  156.     return 0;
  157. }
  158.  
Success #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
4
267 157 188 259
193 320 346 12
stdout
copy 
YES
93 100 62 12
0 57 100 0
0 88 100 0
100 75 84 0
https://ideone.com/i9l3zW
language:
C++14 (gcc 8.3)
created:
6 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!