Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2017
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.51 KB | None | 0 0
  1. #include <iostream>
  2. #include <cassert>
  3. #include <vector>
  4.  
  5. #define ll long long
  6. #define mp make_pair
  7. #define pb push_back
  8. #define f first
  9. #define s second
  10. #define vi vector<int>
  11. #define vl vector<long long>
  12. #define sz(a) (int)((a).size())
  13. #define all(a) (a).begin(),(a).end()
  14. #define pii pair<int, int>
  15. #define pll pair<ll, ll>
  16. #define ld long double
  17.  
  18. using namespace std;
  19.  
  20. const int INF = 1e9;
  21. const int N = 200;
  22. const int M = 200;
  23.  
  24. struct edge {
  25.     int a, b, can;
  26.     edge(int a, int b, int can) : a(a), b(b), can(can) { }
  27. };
  28.  
  29. int n, m;
  30. int prob[M], team[N];
  31. int S, T;
  32. int q[N + M], d[N + M];
  33. int pt[N + M];
  34. vector < edge > edges;
  35. vector < int > g[N + M];
  36. char ans[N][M];
  37.  
  38. void add_edge(int a, int b, int cap) {
  39.     //cerr << a << " " << b << " " << cap << endl;
  40.     g[a].pb(sz(edges));
  41.     edges.pb( edge(a, b, cap) );
  42.     g[b].pb(sz(edges));
  43.     edges.pb( edge(b, a, 0) );
  44.     //cerr << a << " " << b << " " << cap << endl;
  45. }
  46.  
  47. bool bfs() {
  48.     int ql = 0, qr = 0;
  49.     q[qr++] = S;
  50.     memset(d, -1, sizeof d);
  51.     d[S] = 0;
  52.     while(ql < qr) {
  53.         int v = q[ql++];
  54.         for(int id : g[v]) {
  55.             int to = edges[id].b;
  56.             if(d[to] == -1 && edges[id].can > 0) {
  57.                 d[to] = d[v] + 1;
  58.                 q[qr++] = to;
  59.             }
  60.         }
  61.     }
  62.     return d[T] != -1;
  63. }
  64.  
  65. int dfs(int v, int flow) {
  66.     if(flow == 0) return 0;
  67.     if(v == T) return flow;
  68.     for(; pt[v] < sz(g[v]); ++pt[v]) {
  69.         int id = g[v][pt[v]];
  70.         int to = edges[id].b;
  71.         if(d[to] == d[v] + 1) {
  72.             if(int pushed = dfs(to, min(flow, edges[id].can))) {
  73.                 edges[id].can -= pushed;
  74.                 edges[id ^ 1].can += pushed;
  75.                 return pushed;
  76.             }
  77.         }
  78.     }
  79.     return 0;
  80. }
  81.  
  82. int dinic() {
  83.     int flow = 0;
  84.     while(bfs()) {
  85.         memset(pt, 0, sizeof pt);
  86.         while(int pushed = dfs(S, INF)) {
  87.             flow += pushed;
  88.         }
  89.     }
  90.     return flow;
  91. }
  92.  
  93. int main() {
  94.     ios_base::sync_with_stdio(0);
  95.     cin.tie(0);
  96.    
  97.     int first = 1;
  98.     while(cin >> n >> m && !(n == 0 && m == 0)) {
  99.         if(!first) cout << "\n";
  100.         first = 0;
  101.        
  102.         int sum1 = 0;
  103.         for(int i = 1; i <= n; ++i) {
  104.             cin >> team[i];
  105.             sum1 += team[i];
  106.         }
  107.        
  108.         int sum2 = 0;
  109.         for(int i = 1; i <= m; ++i) {
  110.             cin >> prob[i];
  111.             sum2 += prob[i];
  112.         }
  113.         if(sum1 != sum2) {
  114.             cout << "Impossible\n";
  115.             continue;
  116.         }
  117.        
  118.         for(int i = 0; i <= n + m + 1; ++i)
  119.             g[i].clear();
  120.         edges.clear();
  121.        
  122.         S = 0;
  123.         for(int i = 1; i <= n; ++i)
  124.             add_edge(S, i, team[i]);
  125.         T = n + m + 1;
  126.         for(int i = 1; i <= m; ++i)
  127.             add_edge(n + i, T, prob[i]);
  128.         for(int i = 1; i <= n; ++i)
  129.             for(int j = m; j >= 1; --j)
  130.                 add_edge(i, n + j, 1);
  131.        
  132.         int max_flow = dinic();
  133.         if(max_flow != sum1) {
  134.             cout << "Impossible";
  135.         } else {
  136.             for(int i = 1; i <= n; ++i)
  137.                 for(int j = 1; j <= m; ++j)
  138.                     ans[i][j] = 'Y';
  139.             for(int i = 1; i <= n; ++i) {
  140.                 for(int id : g[i]) {
  141.                     int j = edges[id].b;
  142.                     if(j == S || j == T) continue;
  143.                     bool flag = false;
  144.                     if(edges[id].can == 0) {
  145.                         add_edge(S, i, 1);
  146.                         add_edge(j, T, 1);
  147.                         edges[id].can = edges[id ^ 1].can = 0;
  148.                         if(dinic() > 0)
  149.                             flag = true;
  150.                         else {
  151.                             edges[sz(edges) - 4].can = 0;
  152.                             edges[sz(edges) - 3].can = 0;
  153.                             edges[sz(edges) - 2].can = 0;
  154.                             edges[sz(edges) - 1].can = 0;
  155.                         }
  156.                     } else {
  157.                         flag = true;
  158.                     }
  159.                     edges[id].can = edges[id ^ 1].can = 0;
  160.                     if(flag) cout << 'N';
  161.                     else cout << 'Y';
  162.                 }
  163.                 cout << "\n";
  164.             }
  165.             /*
  166.             for(int i = 1; i <= n; ++i, cout << "\n")
  167.                 for(int j = 1; j <= m; ++j)
  168.                     cout << ans[i][j];
  169.              */
  170.            
  171.         }
  172.     }
  173.    
  174.     return 0;
  175. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement